算法复杂度

  算法复杂度分为时间复杂度和空间复杂度。一般对于某个算法来说，我们更关注它的性能，也即时间复杂度。本篇主要讲时间复杂度。

  《大话数据结构》里面对于算法时间复杂度的定义为：

  在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。

算法时间复杂度的表示与推导

  算法时间复杂度一般用O记法来表示。推导大O阶的过程如下：

  1.用常数1取代运行时间中的所有加法常数；

  2.在修改后的运行次数函数中，只保留最高阶项；

  3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。

  4.最终得到的结果就是大O阶。

  算法时间复杂度效率由高到低可排列为：

  O(1) > O(logn) > O(n) > O(nlogn) > O(n2) > O(n3) > O(2的n次方) > O(n!) > O(n的n次方)

  时间复杂度又分为最好情况、最坏情况、平均情况。

常见算法的时间复杂度（平均情况）分类

  常数阶O(1)：数组中查找指定下标的值、hash表

  对数阶O(logn)：二分法

  线性阶O(n)：链表查找某个值

  O(nlogn)：堆排序、快速排序、归并排序

  平方阶O(n2)：直接插入排序、直接选择排序、冒泡排序

  O(n3) ：暂无

  O(2的n次方) ：暂无

  O(n!) ：暂无

  O(n的n次方)：暂无