[专业知识001] 算法设计与分析

算法时间复杂度

🏡 More records...

Get the knowledge flowing and circulating! :)

目录

算法 & 算法复杂度

算法是解决某个问题的计算方法和步骤，是一个计算过程，这个过程中会包括一系列解决问题的清晰指令。

算法复杂度是指算法在编写成可执行程序后运行时所需要的时间资源和内存资源。程序的时间开销和内存开销分别使用时间复杂度和空间复杂度描述。

时间复杂度

概念

一般来说，时间复杂度是一个关于问题规模 $n$$n$ 的函数，记作 $T(n)$$T(n)$。

例1：在计算$1+2+3+...+n$$1+2+3+...+ n$ 的代码中，$T(n)$$T(n)$的表达式如下。

例2：代码功能是$(1\ast 1+1\ast 2+...+1\ast n)+(2\ast 1+2\ast 2+...+2\ast n)+...+(n\ast 1+n\ast 2+...+n\ast n)$$(1*1+1*2+...+1*n) + (2*1+2*2+...+2*n) +...+ (n*1+n*2+...+n*n)$

在大多数情况下，分析算法的时候，我们并不需要精确的计算出 $T(n)$$T(n)$ 的函数表达式，我们只需要研究算法在最坏情况或者平均情况下的算法复杂度，另外如果问题规模 $n$$n$ 是一个很小的数字，那么显然就没有必要讨论解决该问题的时间复杂度了。

分析方法

所以，通常情况，我们在研究某个算法时，输入的时间规模 $n$$n$ 满足 $n>>1$$n>>1$，即，$n$$n$ 是一个非常大的数字。这里需要引入描述时间复杂度的三种最常使用的符号：$O$$O$, $\mathrm{\Omega }$$\Omega$, $\mathrm{\Theta }$$\Theta$。

$O$$O$：代表时间复杂度的渐进上界

$\mathrm{\Omega }$$\Omega$：代表时间复杂度的渐进下界

$\mathrm{\Theta }$$\Theta$：代表时间复杂度的渐进确界

• $O$$O$：代表时间复杂度的渐进上界

  已知$T(n)$$T(n)$是某种算法的时间复杂度，$a$$a$是常数，$f(n)$$f(n)$是关于$n$$n$的函数：

  如果对于任意$n(n>>1)$$n(n>>1)$，都有$T(n)<=a\ast f(n)$$T(n)<=a*f(n)$，则称$T(n)=O(f(n))$$T(n)=O(f(n))$。

  比方说，$T(n)=a\ast n^2+b\ast n+c$$T(n)=a*n^2 + b*n + c$，这个时候如果 $n$$n$ 是一个非常大的数字，由于 $n^2$$n^2$ 增长要远大于$n$$n$加常数的增长，所以 $bn+c$$bn+c$ 可以被忽略掉 → $T(n)=a\ast n^2$$T(n)=a*n^2$，那么$T(n)$$T(n)$就可以表示为$O(n^2)$$O(n^2)$了。

• $\mathrm{\Omega }$$\Omega$：代表时间复杂度的渐进下界

  存在$b$$b$是常数，$g(n)$$g(n)$是关于$n$$n$的函数：

  对于任意$n(n>>1)$$n (n>>1)$，都有$T(n)>=b\ast g(n)$$T(n)>=b*g(n)$，则称$T(n)=\mathrm{\Omega }(g(n))$$T(n)=\Omega(g(n))$。

• $\mathrm{\Theta }$$\Theta$：代表时间复杂度的渐进确界

  如果$T(n)$$T(n)$的渐进上界是$O(f(n))$$O(f(n))$ && $T(n)$$T(n)$的渐进下界是$\mathrm{\Omega }(f(n))$$\Omega(f(n))$，那么

  $$T(n)=O(f(n))\mathrm{\&}\mathrm{\&}T(n)=\mathrm{\Omega }(f(n))\to T(n)=\mathrm{\Theta }(f(n))$$

对于大部分的算法分析，我们只需要关注算法的渐进上界，即，使用 $O$$O$ 表示算法复杂度。

这是因为，大家在使用算法的时候，几乎不会考虑下界$\mathrm{\Omega }$$\Omega$的，因为如果人们说，请设计一个$O(n)$$O(n)$的算法，大家希望得到的算法满足最坏情况下不超过$O(n)$$O(n)$，如果这个时候设计出一个$O(\log n)$$O(\log n)$的算法，肯定也是满足需求的。人们也不会表达说，需要 $n$$n$但不需要$\log n$$\log n$的算法；这种情况换一种说法，当人们说，这种算法是$O(n\log n)$$O(n \log n)$的时候，希望表达的是这个算法至少是$O(n\log n)$$O(n \log n)$，不会比$O(n\log n)$$O(n \log n)$差（比如，$O(n^2)$$O(n^2)$）。

算法时间复杂度排序：$O(1)$$O(1)$ < $O(\log n)$$O(\log n)$ < $O(n)$$O(n)$ < $O(n\log \log n)$$O(n \log \log n)$ < $O(n\log n)$$O(n \log n)$ < $O(n^2)$$O(n^2)$

总结 所以，我们在分析算法时间复杂度的时候，能够将算法使用 $O$$O$ 表示就行了。在表示的过程中，我们会忽略公式中的低阶项、常量和系数，只记录最大阶的量级，所以我们在分析算法时间复杂度的时候，只关注循环执行次数最多的那一段代码就可以了。

例如：在下面这段代码中，c1, c2, c9都是常量级执行时间；c3, c4, c8对应 $n$$n$ ；c5, c6, c7对应 $n^2$$n^2$ 。我们重点要分析c5, c6, c7这一段，最后得到整体的时间复杂度为 $O(n^2)$$O(n^2)$。

虽然说，代码千差万别，但是常见的时间复杂度并不多。↓

常见算法时间复杂度

通常情况下，这些算法时间复杂度可以覆盖全部面试中可能碰到的问题的时间复杂度

• 常量复杂度$O(1)$$O(1)$，它是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。比方说，在代码当中有3行，也是$O(1)$$O(1)$的时间复杂度，总结来说，只要代码的执行时间不随问题规模的增大而增长，那么时间复杂度就是$O(1)$$O(1)$。一般情况下，如果算法当中不存在循环和递归，那么该算法的复杂度就是$O(1)$$O(1)$;

• $O(\log n)$$O(\log n)$和$O(n\log n)$$O(n \log n)$是对数时间复杂度。

  • 很多经典的算法都是对数时间，例如二分查找、快速排序、二叉搜索树等等。

    例如：在下面这段代码中，累加1、2、4、8...一直到$2^x$$2^x$，其中$2^x<=n$$2^x<=n$，该算法的时间复杂度就是$O(\log n)$$O(\log n)$，因为 $i$$i$ 是以2的指数增长。如果循环执行 $x$$x$ 次，而$2^x<=n$$2^x<=n$，所以 $x={\log }_{2}n$$x={\log_2}n$；

    

  • 对于$O(n\log n)$$O(n \log n)$通常情况下是执行了 $n$$n$ 次的$O(\log n)$$O(\log n)$算法，例如，对一个长度为 $n$$n$ 的数组进行 $n$$n$ 次二分查找，时间复杂度就是$O(n\log n)$$O(n \log n)$。

    

• ▲对于$O(n)$$O(n)$，$O(n^2)$$O(n^2)$，$O(n^3)$$O(n^3)$，$O(n+m)$$O(n+m)$，$O(nm)$$O(nm)$都是一般形式的多项式量级复杂度。它们大部分和循环的层数相关，例如，一层循环的遍历是$O(n)$$O(n)$，二层是$O(n^2)$$O(n^2)$，三层是$O(n^3)$$O(n^3)$。

  

  ◆而如果输入数据有两个变量，就会出现$O(n+m)$$O(n+m)$和$O(nm)$$O(nm)$的情况了。

  

• 对于指数级和阶乘时间复杂度，一般为$O(2^n)$$O(2^n)$与$O(n!)$$O(n!)$。

  这种非多项式量级的算法问题被称为NP问题，也就是Non-Deterministic Polynomial(非确定多项式问题)。

  • 当数据规模 $n$$n$ 增大的时候，非多项式量级的算法执行时间会急剧增加，求解问题的执行时间就会无限增长。

  • 所以非多项式时间复杂度的算法是非常低效的。暴力回溯法可能会出现 $O(2^n)$$O(2^n)$ 这种时间复杂度，某些图算法也会出现 $O(n!)$$O(n!)$ 复杂度。

  deterministic 美/ dɪˌtɜːrmɪˈnɪstɪk / adj.确定性的；命运注定论的

  The rise or decline of the United States is not a function of deterministic forces.

  美国的兴衰不是不可抗拒力的作用。

  non-deterministic

  • adj.非确定的

  • n.不确定性；非决定性

  Works by capturing, recording and replaying non-deterministic events and inputs.

  通过捕获、记录和重现非决定性的时间和输入而工作。

  polynomial 美/ ˌpɑːliˈnoʊmiəl /

  • adj.多项的，多词的；多项式的

  • n.多项式；多词拉丁学名；表示任何多项数之和

  Based on the relationship between the group delay function and the cepstral coefficients, the denominator polynomial coefficients can be determined.

  根据群延迟函数与倒谱系数之间的关系，可以确定分母的多项式系数。

总结来说，经典算法中最常出现的算法复杂度是$O(1)$$O(1)$, $O(\log n)$$O(\log n)$, $O(n)$$O(n)$, $O(n\log n)$$O(n \log n)$, $O(n^2)$$O(n^2)$这5个，而掌握算法复杂度最好的方法就是掌握各类经典算法的实现方法，并且通过练习来熟练掌握。