大 O 符号

函数 g(n)g(n) 是函数 f(n)f(n) 的渐进上界 aymptotic upper bound 表述为

f(n)=O(g(n))f(n)= O(g(n))

如果有 正常数 cc 与 n0n_0 使得 0≤f(n)≤cg(n)0 \le f(n) \le cg(n) 对所有 n≥n0n \ge n_0
即 lim⁡sup⁡n→∞f(n)g(n)<∞\lim\sup_{n\to \infty}\frac{f(n)}{g(n)} < \infty

集合表述法

O(g(n))O(g(n))表示函数集合 O(g(n))={f(n)∣∃ c,n0>0 s.t. 0≤f(n)≤cg(n) for n≥n0}O(g(n)) = \{f(n) |\exists\ c,n_0 > 0\ \text{s.t.}\ 0\le f(n) \le cg(n)\ \text{for}\ n\ge n_0\}
所以很多时候我们也写成 f(n)∈O(g(n))f(n) \in O(g(n))

大 Ω\Omega 符号

对于函数 g(n)g(n) 是一个 渐进下界 f(n)f(n) 表述为

f(n) = \Omega(g(n))$$ 表示存在一个常数 $c$ 和 $n_0$ 使得 $0 \le cg(n) \le f(n)$ 对所有 $n \ge n_0$ 即 $\lim\inf_{n\to \infty}\frac{f(n)}{g(n)} > 0$ ## 大 $\Theta$ 符号 对于函数 $g(n)$ 是一个渐进紧密界 $f(n)$ 表述为 $$f(n) = \Theta(g(n))$$ 表示存在常数 $c_1,c_2$ 和 $n_0$ 使得 $0 \le c_1g(n) \le f(n) \le c_2g(n)$ 对所有 $n \ge n_0$ ### $\Theta$ 定理 $$\Theta(g(n)) = O(g(n)) \cap \Omega(g(n))

排序算法的复杂度分析

比较次数定理

对于 n 个元素，任意对比算法最多需要 Ω(nlg⁡n)\Omega(n\lg n) 次比较

证明

由于合格的排序算法需要能提供所有的排列可能性，即我们化成决策树的形式，就会有 n!n! 种叶子，连接这些叶子，那么对于二叉树

斯特林公式

如何计算 (nk)\begin{pmatrix} n \\ k \end{pmatrix} 如果当 n,kn,k 非常大的时候？

阶乘的拟合

n!∼2πn(ne)nn! \sim \sqrt{2\pi n}(\frac{n}{e})^n

这是离散形式的渐进拟合，这个公式在n很小的时候也十分接近原函数
但是我们可能对连续的函数更感兴趣，即

\Gamma(x) = \int_0^{\infty} t^{x-1}e^{-t}dt $$ 那么我们可以化简这个积分公式 $$ n! = \int_0 ^{\infty} x^n e^{-x}dx = \int_0^{\infty} e^{n\ln x - x}dx

然后，设 f(x):=x−nln⁡xf(x):= x - n\ln x 那么我们求导，得到 f′(x)=1−nx=0⇒x=nf'(x) = 1 - \frac{n}{x} = 0\Rightarrow x = n 那么我们可以得到 f(x)f(x) 在 x=nx = n 处取得最小值，并且对于二阶导 f′′(x)=nx2∣x=n=1nf''(x) = \frac{n}{x^2} |_{x=n} = \frac 1 n 是一个凸函数
因此我们使用 −f-f 找到最小值，因此，我们可以在这里使用泰勒展开:

f(x)∼n−nln⁡n+121n(x−n)2f(x)\sim n - n\ln n + \frac 1 2 \frac 1 n (x-n)^2

因此我们将这个公式带回原积分公式 ∫0∞enln⁡x−xdx∼∫0∞enln⁡n−n−121n(x−n)2dx∼12enln⁡n−n∫0∞e−121n(x−n)2dx∼12e−nnn2πn\int_0^\infty e^{n\ln x - x}dx \sim \int_0^\infty e^{n\ln n - n - \frac 1 2 \frac 1 n (x-n)^2}dx \sim \frac{1}{2} e^{n\ln n - n}\int_0^\infty e^{-\frac 1 2 \frac 1 n (x-n)^2}dx \sim \frac{1}{2} e^{- n}n^n\sqrt{2\pi n}

主定理 Master Theorem

如果函数 T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n) 那么

  1. T(n)=Θ(nlog⁡ba)T(n) = \Theta(n^{\log_b a}) 如果 f(n)=O(nlog⁡ba−ϵ)f(n) = O(n^{\log_b a - \epsilon}) for some ϵ>0\epsilon > 0
  2. T(n)=Θ(nlog⁡balog⁡n)T(n) = \Theta(n^{\log_b a} \log n) 如果 f(n)=Θ(nlog⁡ba)f(n) = \Theta(n^{\log_b a})
  3. T(n)=Θ(f(n))T(n) = \Theta(f(n)) 如果 f(n)=Ω(nlog⁡ba+ϵ)f(n) = \Omega(n^{\log_b a + \epsilon}) for some ϵ>0\epsilon > 0 且如果 af(n/b)≤cf(n)af(n/b) \leq cf(n) 对某些 c<1c < 1 与足够大的 nn