## 什么是时间复杂度？

在计算机科学中，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 n （必须比 n₀ 大）的输入，它至多需要 5n³ + 3n 的时间运行完毕，那么它的渐近时间复杂度是 O(n³)。

——维基百科

抓出第一句话的主谓宾，我们可以把这句话缩为“**时间复杂度是函数**”。所以说，时间复杂度本质上是一个**函数**（本文记作$ T(n) $，代表输入大小为$n$的情况下的效率），而对于算法时间复杂度的研究实际上也就是对一个特殊的函数的研究。

而想要了解算法性能我们就可以对其时间复杂度进行渐近分析。（也就是渐进时间复杂度）

这里就可以引出一组数学概念了——渐近记号$ o、w、Θ、O、Ω $

## 渐近精确记号（$ Θ $ ）
对于函数$ f(x),g(x)(x\in N) $ ,如果$ \displaystyle\lim_{x\rightarrow ∞}\dfrac{f(x)}{g(x)} $ 存在，并且等于某个常数$ c(c>0) $ ，那么我们说$ f(x)=Θ(g(x)) $ 。通俗来讲就是两个函数同数量级，$ g(x) $ 称为$ f(x) $ 的渐近紧确界，这个符号就可以表示算法的精确阶。

这个记号还有一个定义方法可能更容易理解，如下图：

也就是定义正常量$ c_1,c_2,x_0 $ ，使得所有$ x\ge x_0,\exists c_1f(x)\le g(x)\le c_2f(x) $ 。

更粗暴的来讲，就是说过了图上那个标记的点，那根黄色的函数就穿不过去绿色和灰色的函数了。

这可以用高中的选修知识证明。

这也是用于表达算法复杂度最严谨的方法了。

## 渐近上界记号（$ O $ ）：

这是最常用的算法复杂度分析方法。

理解了渐近紧确记号其实也就接着理解了接下来的几个记号。对于渐近上界记号而言我们其实可以把它类比为小于等于号。

同样的，对于函数$ f(x),g(x)(x\in N) $ 。若$ \exists x_0,c\in N $ ，使得对一切$ x\ge x_0 $ 都有$ 0\le f(x)\le cg(x) $ 成立，则称$ f(x) $ 的渐进的上界是$ g(x) $ ，记作$ f(x)=O(g(x)) $ 。

在图像上粗暴的来理解就是永远穿不过上面那一根函数（比如上图那根黄色的永远穿不过灰色的）。

渐近上界可以同时有很多个，我们往往选择最贴近的那一个，也就是数量级（阶）最低的那一个。

## 非渐近紧确上界记号（$ o $ ）：

去掉了一个紧确。比如$ 2x=o(x^2)\doteq o(x) $ 。

## 渐近下界记号（$ Ω $ ）：

也就是描述函数数量级最小不小于什么的。

图像上（还是以上图为例）也就表现为黄色的函数永远比绿色的函数高。

## 非渐近紧确下界记号（$ ω $ ）

和非紧确上界一样的理解方式，比如$ x^2=ω(x)\doteq ω(x^2) $ 。

---

## 参考资料

* 维基百科
* [https://blog.csdn.net/so_geili/article/details/53353593](https://blog.csdn.net/so_geili/article/details/53353593)
如有错误之处，望指出。