Question

如何分析算法的复杂度

Answer 1

算法的复杂性
算法的复杂性是算法效率度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。
计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。
不言而喻，对于任意给定的问题，设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。
简言之，在算法学习过程中，我们必须首先学会对算法的分析，以确定或判断算法的优劣。
1.时间复杂性：
例1：设一程序段如下（为讨论方便，每行前加一行号）
(1) for i:=1 to n do
(2) for j:=1 to n do
(3) x:=x+1
......
试问在程序运行中各步执行的次数各为多少？
解答：
行号 次数(频度)
(1) n+1
(2) n*(n+1)
(3) n*n
可见，这段程序总的执行次数是：f(n)=2n2+2n+1。在这里，n可以表示问题的规模，当n趋向无穷大时，如果 f(n)的值很小，则算法优。作为初学者，我们可以用f(n)的数量级O来粗略地判断算法的时间复杂性，如上例中的时间复杂性可粗略地表示为T(n)=O(n2)。

Answer 2

算法复杂度分析是指算法所需要的计算机资源，一个算法的评价主要从时间复杂度和空间复杂度来考虑。时间复杂度是指执行算法所需要的计算工作量；空间复杂度是指算法所需要消耗的内存空间。
参考资料：《大学计算机-计算思维导论》，清华大学出版社2019