跳到主要内容

算法复杂度分析

时间复杂度分析​

渐进分析 Asymptotic analysis

上界 O-natation: Upper-Bound​

如果存在 c>0,n0>0c>0,n_0>0，对于所有的 n≥n0n\ge n_0 都有 0≤f(n)≤cg(n)0\le f(n) \le cg(n)，则f(n)=O(g(n))f(n) = O(g(n))

比如说 2n2=O(n3)2n^2 = O(n^3)，我们取c=1,n0=2c=1,n_0=2

下界 Ω-notation (lower bounds)​

如果存在 c>0,n0>0c>0,n_0>0，对于所有的 n≥n0n\ge n_0 都有 0≤cg(n)≤f(n)0\le cg(n) \le f(n)，则 f(n)=Ω(g(n))f(n) = Ω(g(n))

比如说 n=Ω(lg⁡n)\sqrt{n} = \Omega(\lg n)，我们取c=1,n0=16c=1,n_0=16

渐进界 Θ-notation (tight bounds)​

如果存在 c1>0,c2>0,n0>0c_1>0,c_2>0,n_0>0，对于所有的 n≥n0n\ge n_0 都有 0≤c1g(n)≤f(n)≤c2g(n)0\le c_1g(n) \le f(n) \le c_2g(n)

比如说 n2+2n=Θ(n2)n^2+2n = Θ(n^2)

正确性分析与证明、时间复杂度分析、空间复杂度分析、最坏情况分析、平均情况分析、聚合分析