数据结构时间复杂度

数据结构时间复杂度

时间复杂度是同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。

计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。

数据结构的定义问题

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

常用结构：数组、栈、队列、链表、树、图、堆、散列表。

重要意义：一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率。

数据结构哈夫曼树

数据结构哈夫曼树是由德国数学家冯·哈夫曼发现的，又称为最优二叉树，是一种带权路径长最短的树结构。哈夫曼树的特点是引出的路程最短，哈夫曼树的形状是单支形式，对于编程具有重大的意义，使某些很难完成的任务变得简单，可以有条理的完成。树的路径长度是从树根到每一个叶子之间的路径长度之和，节点的带树路径长度为从该节点到树根之间的路径长度与该节点权的乘积。