跳到主要内容

算法分析

时间复杂度​

n:输入规模n\text{:输入规模}
T(n):算法的时间复杂度T(n)\text{:算法的时间复杂度}

最佳情况​

一般不进行算法在最佳情况下的分析

最坏情况​

通常与平均情况下的时间复度一致

平均情况​

T(n)=∑i=1mpitiT(n)=\sum^{m}_{i=1}p_it_i
输入分为m类 第i类输入发生的概率pi 第i类输入执行的时间ti\text{输入分为}m\text{类}\text{ 第}i\text{类输入发生的概率}p_i\text{ 第}i\text{类输入执行的时间}t_i

渐进记号​

只关心算法运行时间如何随输入规模的无限增长而增长

O\Omicron​

g(n),O(g(n))={f(n):∃c,n0→∀n≥n,0≤f(n)≤cg(n)}g(n), \Omicron(g(n))=\{f(n):\exists c,n_0 \to \forall n \ge n, 0 \le f(n) \le cg(n)\}

给出算法运行时间的渐进上界

Ω\Omega​

g(n),Ω(g(n))={f(n):∃c,n0→∀n≥n0,0≤cg(n)≤f(n)}g(n), \Omega(g(n))=\{f(n):\exists c,n_0 \to \forall n \ge n_0, 0 \le cg(n) \le f(n)\}

给出渐进下界

Θ\Theta​

g(n),Θ(g(n))={f(n):∃c1,c2,n0→∀n≥n0,0≤c1g(n)≤f(n)≤c2g(n)}g(n), \Theta(g(n))=\{f(n):\exists c_1,c_2,n_0 \to \forall n \ge n_0, 0 \le c_1g(n) \le f(n) \le c_2g(n)\}

给出渐进紧致界