本文主要书写了本人对于算法复杂度的一些理解,并辅以一些例子进行说明

算法复杂度的概念

复杂度的计算理念

  • 我们不对某个算法进行精确的分析,只需要初略地知道它的增长趋势就可以了。
  • 平常我们分析算法复杂度的时候,通常有分析最坏情况和平均情况两种选项,由于最坏情况易于分析,所以我们一般分析算法复杂度的最坏情况。

复杂度的渐进表示法

  • 上界

$$ T(n) = O(f(n)) $$

上述式子表示当N足够大的时候,f(n)函数是T(n)的上界。

  • 下界

$$ T(n) = \Omega(h(n)) $$

上述式子表示当N足够大的时候,h(n)函数是T(n)的下界。

  • 上界和下界同时成立

$$ T(n) = \Theta(g(n)) $$

上述式子表示当N足够大的时候,g(n)函数同时是T(n)的上界和下界。

  • 在上面三个式子中,T(n)表示的都是某个算法的时间复杂度,它们也可以应用在算法的空间复杂度S(n)上。
  • 一个算法的上界和下界函数可能有无穷多个,为了和现实的情况更贴合,我们在使用上述式子表示算法的复杂度的时候,通常使用最小的上界最大的下界

复杂度的增长趋势比较

$$ O(1) < O(\log N) < O(n) < O(n \log N) < O(n^2) < O(n^3) < O(2^N) < O(n!) $$

复杂度计算理念的进一步说明

由于我们分析算法复杂度的时候主要是分析它的增长趋势,所以我们只需要分析算法复杂度的某个主要趋势即可。

例一

有时间复杂度计算公式,$$ T(n) = C_1 * n^2 + C_2 * n $$

在N进行增长的时候,$n^2$对于T(n)增长的影响是远远大于$n$的,所以我们就可以忽略掉$n$,认为$$ T(n) = C_1 * n^2 $$ 或者记做 $$ T(n) = O(n^2) $$ 即当N很大的时候,$n^2$为T(n)的上界函数。

例二

当我们谈论时间复杂度$\log N$的时候,我们并没有说明$ \log N$是以2,以10还是以e为底的。这是因为当N很大的时候,$ \log_2 N $和$ \log_10 N $它们之间相差了常数倍,$ \log N $的增长趋势是大于常数的增长趋势的,所以我们可以忽略掉底数的差异,直接以$ \log N $ 代指一种增长趋势。

复杂度分析小窍门

有两个时间复杂度T1T2

$$ T_1(n) = O(f_1(n)), T_2(n) = O(f_2(n)) $$

$$ 1. \space \space T_1(n) + T_2(n) = max(O(f_1(n)), O(f_2(n))) $$ $$ 2. \space \space T_1(n) * T_2(n) = O(f_1(n) * f_2(n)) $$

根据公式1,我们可以得到当T(n)是关于n的k阶多项式的时候,$ T(n) = \Theta(n^k) $

于是可得:

1
2
3
一个for循环的复杂度 = 循环体的复杂度 * 循环次数

一个if-else的复杂度 = max(条件判断式的复杂度,if分支的复杂度,else分支的复杂度)