# 什么是时间复杂度
时间复杂度是使用数学公式的方式,对计算机学科中的数据结构、算法的性能衡量方法。
对于具体方法或者算法的入参数量使用n替代,基于入参完成具体功能所需要的时间记为函数T(n)。
T(n)是以n变量或者常数构成的函数。
# 常见的时间复杂度
在大学的数据结构课程里,都会介绍不同的数据结构如树结构、表、堆栈,以及几大排序算法的时间复杂度。常见的复杂度运行时间和名称如下:
| 名称 | 运行时间:T(n) |
|---|---|
| 常数时间 | O(1) |
| 线性时间 | O(n) |
| 对数时间 | O(logN) |
| 线性对数时间 | O(NlogN) |
| 二次时间 | O(N^2) |
| 三次时间 | O(N^3) |
不同运行时间的优劣比较:
前面说过,时间复杂度是以n或者常数为变量的函数,为什么这里变成了T(n)=O(1),T(n)=O(n) ,而不是T(n)=1,T(n)=n。
O(n)称之为大O表示法。
# 大O表示法
我们把T(n)=n,T(n)=2*n+1等等一次函数统表示为T(n)=O(n),称为大O表示法。
原始的函数表达式如何转换为大O表示法呢?
使用的主要数据概念是极限。
假设某算法的原始复杂度为:T(n)=10n+1
当n=>无穷大的时候,10n+1 约等于 n。
所以,为了表示的统一性,使用了大O表示法。
即T(n)=100n+10=O(n),T(n)=10logN+1=O(logN)。
所以在看到大O表示法的时候,是有一个隐含的条件的,即在n为极限的情况:n=>无穷大。
T(n)=O(logN),读作在N无穷大时,时间复杂度为logN。
# 极限与级数的运用
在现代的数学分析教科书中，几乎所有基本概念（连续、微分、积分）都是建立在极限概念的基础之上
极限是指数据个数n为无穷大时,算法的时间复杂度,这样得出的时间复杂度具有普适性。
# 常见数据结构&算法的时间复杂度计算
# 折半查找
如数组只有两个元素,最坏情况下折半查找一次。如果数组有四个元素,最坏情况折半查找为两次,则公式为:
N*(1/2)^x=1,其中,N为待查找元素个数,x为最坏查找次数。
转换结果x=logN。底数为2。
即,折半查找的时间复杂度为:O(logN)
# 完全排序二叉树查找
对于完全排序二叉树,假设树的高度为h。那么在树的第h层的节点个数为:2^(h-1)
那么这样整个h深度的树的总结点个数为:N=1+2+4+...+2^(h-1)
等式左右两边都乘以2,得:2N=2+4+...+2^(h-1)+2^h
相减,变换,得:h=log(N+1)。
即,完全二叉树的查找时间复杂度为:O(logN)