数据结构中的几种时间复杂度分析方式

前言

时间复杂度，顾名思义，就是计算（说是预估可能更为准确）程序中运行所消耗的时间，数据结构中计算时间复杂度分别有以下方式：

1. O
2. Ω
3. θ
4. o

大O表示法（渐进上界（最坏情况））

定义：如果存在正常数c和n₀使得当N ≥ \geq≥ n₀ 时，T(N) ≤ \leq≤ cf(N)，则记为T(N) = O(f(N));

如图所示，当N大于等于某个常数之后，cf(N)某一部分可以看成T(N)的上界，cf(N)始终大于T(N)

大Ω表示法（渐进下界（最好情况））

定义：如果存在正常数c和n₀使得当N ≥ \geq≥ n₀ 时，T(N) ≥ \geq≥ cg(N)，则记为T(N) = Ω(g(N));

如图所示，当N大于等于某个常数之后，cg(N)某一部分可以看成T(N)的下界，cg(N)始终大于T(N)

假如T(N)代表某一个算法对于规模为N个输入数据所需要的处理时间，即处理N个数据所需要花费的时间为T(N)，T(N)可能是非常复杂的，如上述两图，T(N)可能会存在上下波动的情况，显然不如f(N)与g(N)看着简洁，所以我们通常用f(N)与g(N)这样的更简单的函数来估计T(N)。

那么用f(N)与g(N)哪个函数来估计T(N)更好呢？假如boss要求你估计你算法的执行时间，如果回答cg(N),那么就太不谦虚了，且真正的执行时间T(N)还大于cg(N)，如果用cg(N)来代表预估的执行时间，那么真正的执行时间T(N)永远达不到所预估的执行时间cg(N)，直接被炒鱿鱼了。所以应该用真正的执行时间T(N)的上界，即cf(N)来代表预估的执行时间，这样才是准确的，因为这个情况下才能达到目标值，实际执行时间T(N)会比预估的执行时间cf(N)要少

所以我们预估算法的执行时间的时候，通常是取上界而不是下界（因为算法实际耗时可能要比下界多得多）

所以通常情况下预估算法执行时间和效率，我们会用大O表示法，即第一种方法，T(N)=O(f(N))

θ表示法（渐进上下界）

定义：T(N) = θ(h(N))，当且仅当T(N) = O(h(N))且T(N) = Ω(h(N));

这个的意思是，h(N)既是T(N)的上界又是T(N)的下界，即h(N)在某种情况下与T(N)重合了。

我们发现，在这种情况下，用h(N)来估计T(N)会更准确。我们称T(N)=θ(h(N))为θ表示法。

θ表示法比大O表示法更准确，因为大O表示法仅提供了上界，而θ表示法既提供了上界也提供了下界。

但是为什么平时一般用大O表示法而不用θ表示法呢？因为θ表示法的函数很难找，这一函数几乎和T(N)重合了。（θ读西塔）

小o表示法

定义：如果T(N) = O(p(N))且T(N) ≠ \neq= θ(p(N))，则T(N) = o(p(N))

在N大于等于某个常数的时候，cp(N)是完全大于T(N)的，不存在等于的情况，这种表示法实际上就是把大O表示法的等号去掉了，我们称之为小o表示法。

由此我们可以看出大O表示法的缺点：大O表示法估计出一个上界，但是这个上界不一定是最小上界，没必要紧贴着T(N)。从某种意义上来说，我们用大O表示法估计T(N)的时候，有时候可能会和小o表示法重合，即大O表示法包含小o表示法

如下示例：

T(N) = N 2 N^2N2            f(N) = N 3 N^3N3            T(N) = O(f(N))

f(N)满足大O表示法对T(N)的估计，所以T(N)=O(f(N))完全没问题，只要T(N)小于等于f(N)即可。而小于等于也包括小于的情况，显然大O表示法这样表示是不好的，因为这样表示太谦虚了。因此在实际应用中，我们用大O表示法估计的时候，尽量找最小的上界。而在考研中，我们尽量用θ表示法来估计T(N),这样更准确些

时间复杂度分析的最坏、最好与平均情况

1. 最坏情况指T(N)耗时最大情况，即用大O表示法（考研如果不指定，一般都用这种方法）
2. 最好情况指T(N)耗时最小情况，即用大Ω表示法
3. 平均情况指T(N)耗时平均情况，即用θ表示法