Cameudis's Notes

Appearance

时间复杂度 ​

我们希望能够衡量一个算法的复杂度，并忽略那些和计算机本身相关的参数，只关注抽象的算法性能。因此，我们采用渐进分析（Asymptotic Analysis） 的方法，考虑当问题的输入规模 n 趋向于无穷大时，算法所需时间 T(n) 会如何变化。

渐进分析的几种标记 ​

大 O 表示法 O(n) ​

表示函数的上界。定义为：

f(n)=O(g(n))⟺∃ c,k:(∀ n≥k:0≤f(n)≤cg(n))

大 Ω 表示法 Ω(n) ​

表示函数的下界。定义为：

f(n)=Ω(g(n))⟺∃ c,k:(∀ n≥k:0≤cg(n)≤f(n))

大 Θ 表示法 Θ(n) ​

表示函数的 tight bound，定义为：

f(n)=O(g(n))⟺∃ c1,c2,k:(∀ n≥k:c1g(n)≤f(n)≤c2g(n))

在这几种表示法中，常数项是可以直接扔掉的！我们主要关注的是“变化”。

一个显然的定理：(O&Ω)⟺Θ

计算递归函数的时间消耗 ​

递归函数并不像非递归函数那样直观，我们在计算递归算法的时间复杂度时，可以使用一些特殊的方法。在使用以下方法之前，需要先得到递归函数的时间消耗表达式，如 T(n)=T(n/3)+T(2n/3)+n。

使用迭代法猜测复杂度 ​

我们可以将 T(n) 的表达式使用树形展开，主要观察两点：

  1. 树的每一层会消耗多少时间？
  2. 树一共有多少层？

例如，在 T(n)=T(n/3)+T(2n/3)+n 中，每一层都会独立消耗时间 n，而树一共有 log3/2n 层，因此可以猜测时间复杂度为 O(nlogn)。

使用代入法证明猜测 ​

如果猜测 T(n)=O(nm) ，那么可以“假设 T(k)≤ckm”（或是最高为 m 次的一个以 k 为未知数的多项式），然后尝试证明 T(n)≤ 一个最高为 m 次的以 n 为未知数的多项式。

使用 Master Theorem 秒杀递归函数 ​

之所以 Master Theorem 要叫这个名字，是因为它将递归函数的时间复杂度计算分成了三种情况：

  1. 递归树分支极多，时间消耗由 Leaf 主导；
  2. 递归树分支和每一次递归的开销类似，两者平手；
  3. 递归树的每一次递归合并开销大，时间消耗由 Root 主导。

为了判断究竟属于哪一种情况，首先要把 T(n) 表示成下面这种形式：

T(n)=aT(n/b)+f(n),a≥1,b>1

然后我们比较 f(n) 与 nlogba，就可以分出以下三种情况（与上面所叙述的三种情况对应）：

Case 1: 如果 f(n)=O(nlogba−ϵ)，则有 T(n)=Θ(nlogba)

Case 2: 如果 f(n)=Θ(nlogba)，则有 T(n)=Θ(nlogbalgn)

Case 3: 如果 f(n)=Ω(nlogba+ϵ)，则有 T(n)=Θ(f(n))

摊还分析 ​

我们有时需要计算对于某个数据结构的一系列操作的平均时间。这样，即使一个数据结构的某种操作十分耗时，我们也可以证明平均操作的时间开销并不大。

例如，对于动态改变大小的哈希表，我们就可以使用摊还分析证明其平均操作时间为 O(1)，而不是 O(n2)。

摊还分析的三种方法 ​

三种方法往往都是可用的，但是对于不同的问题，一定会存在一种最适合、最简单的方法。

聚合分析（aggregate analysis）：将所有操作的开销加起来，直接求平均值。

核算法（accounting method）：为不同的操作赋予一个摊还代价，其与实际代价的差值会增减初始值为0的信用。只要我们证明信用总是大于0，就可以证明总摊还代价是总实际代价的上界。

势能法（potential method）：取数据结构的某些特征为参数，构造一个将状态映射到势能值的势能函数 Φ(Di)，并基于势能函数定义摊还代价 ci^=ci+Φ(Di)−Φ(Di−1)。只要我们证明有 Φ(Dn)≥Φ(D0)，就可以证明总摊还代价是总实际代价的上界。

参考资料：