算法时间复杂度

一、常见算法复杂度

O(N!)、O(2^N)、O(N2)、O(NlogN)、O(N)、O(logN)、O(1)...
代表： 最坏情况的用时

二、数学概念科普

1、N! 阶乘

一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。自然数n的阶乘写作n!。1808年，基斯顿·卡曼引进这个表示法。

• 0！=1
• 5！=1×2×3×4×5
• n！=1×2×3×4×....×(n-1)×n

2、2^N / N^2

N 的 N 次方，^ 是上标的意思

• 2^N：2 的 N 次方
• N^2：N 的 2 次方

3、logN 对数函数

如果 aˣ = N（a>0，且a≠1），那么数 x 叫做以 a 为底 N 的对数，记作 x=logaN，读作以 a 为底 N 的对数，其中 a 叫做对数的底数，N 叫做真数。
其中 x 是自变量，函数的定义域是（0，+∞），即 x>0。它实际上就是指数函数的反函数，可表示为 x= aʸ 。因此指数函数里对于 a 的规定，同样适用于对数函数。

• logN：以 2 为底 N 的对数，eg x=logN => 2^X=N => 如果N=256，则X=8，即logN=8

三、时间复杂度

描述算法复杂度时,常用o(1), o(n), o(logn), o(nlogn)表示对应算法的时间复杂度，是算法的时空复杂度的表示。不仅仅用于表示时间复杂度，也用于表示空间复杂度。
O后面的括号中有一个函数，指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。

1、O(N)

时间复杂度为O(n)，就代表数据量增大几倍，耗时也增大几倍，线性增长，比如常见的：

• 遍历算法

2、O(N^2)

时间复杂度O(n^2)，就代表数据量增大n倍时，耗时增大n的平方倍，这是比线性更高的时间复杂度。比如：

• 冒泡排序 ，就是典型的O(n^2)的算法，对n个数排序，需要扫描n×n次。
• 插入排序
• 选择排序

for(int i=0; i<n; i++) { 
  for(int j=i; j<n; j++) { 
    .... 
  } 
} 

3、O(nlogn)

O(nlogn)同理，就是n乘以logn，当数据增大256倍时，耗时增大256*8=2048倍。这个复杂度高于线性低于平方。比如：

• 归并排序 就是O(nlogn)的时间复杂度。

• 快速排序（平均）

  
  O(NlogN).png

4、O(logn)

当数据增大n倍时，耗时增大logn倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。比如：

• 二分查找 就是O(logn)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。(在二分查找算法中前提是假设数据有序)

  
  O(logN).png

5、O(1)

O(1)就是最低的时空复杂度了，也就是耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。 比如：

• 哈希算法 就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（不考虑冲突的话）

四、具体耗时

代入 N 以后的数值，和耗时的关系，10 ^ 8 => 秒级，最大的 N 分别是：

• O(N!) => 10
• O(2^N) => 30
• O(N^2) => 10000
• O(NlogN) => 10^7
• O(NlogN)/O(N) => 10^8
• O(logN) => 天文数字