新加坡

通常，算法的效率或运行时间被表述为输入长度与步骤数(时间复杂度)或存储位置(空间复杂度)之间的函数关系。算法分析是更广泛的计算复杂性理论的重要组成部分，它为解决给定计算问题的任何算法所需的资源提供理论估算。这些估算为寻找高效算法提供了合理的方向。在算法的理论分析中，通常从渐进的意义上估计算法的复杂性，即估计任意大输入的复杂性函数。为此，我们使用了大 O 符号、大欧米茄符号和大θ符号。

经验法则可以通过计算程序的嵌套循环来分析简单程序。对 n 个项目的单个循环产生 f( n ) = n。循环中的循环产生 f( n ) = n3。

经验法则：对于一系列连续的 for 循环，其中最慢的循环决定了程序的渐近行为。两个嵌套循环后接一个单循环，其渐近行为与单独的嵌套循环相同，因为嵌套循环支配着简单循环。

一、分析类型

算法复杂度可以是最佳、平均或最坏情况分析。算法分析可以使用大 O 符号表示。给定算法的最佳、最差和平均情况分别表示资源使用的最少、最多和平均值。大 O 符号简化了算法的比较。

1.最佳情况

计算机科学中的最佳情况性能，用于描述算法在最佳条件下的行为。最佳情况性能的一个例子是尝试使用某种排序算法对已经排序的列表进行排序。例如：[1,2,3] --> [1,2,3] 。

2.平均情况

使用解决问题的平均最优条件来衡量平均情况性能。例如，一个既不是最佳条件也不是最差条件的列表，你希望它按一定顺序排序。例如 [2,1,5,3] --> [1,2,3,5] 或 [ 2,1,5,3] --> [5,3,2,1] 。

3.最差情况

最坏情况性能用于分析算法在最坏输入情况下的行为，以及解决问题的最小可能性。它决定了算法在给定输入条件下何时表现最差。最差情况性能的一个例子是，一个已经按升序排序的姓名列表，你想按降序排序。例如：[Abby, Bill, Catherine] --> [Catherine, Bill, Abby]。

二、递归复杂性

dionyziz

现在让我们来看看递归函数。递归函数是一个调用自身的函数。我们能分析一下它的复杂性吗?下面这个函数是用 Python 写的，用来计算给定数字的阶乘。正整数的阶乘是将它与之前所有的正整数相乘得到的。例如，5 的阶乘是 5 * 4 * 3 * 2 * 1。我们将其表示为 "5!"，并将其发音为 "5 的阶乘"。

1.def factorial( n )：

如果 n == 1：

返回 1 4.

4. 返回 n * factorial( n - 1 )

让我们分析一下这个函数的复杂性。这个函数中没有任何循环，但它的复杂度也不是恒定的。要想知道它的复杂度，我们需要再次计算指令。很明显，如果我们给这个函数传递 n，它就会执行 n 次。如果你对此不确定，现在就 "手动 "运行 n = 5，以验证它是否真的有效。例如，对于 n = 5，它会执行 5 次，因为每次调用都会将 n 减少 1。因此，我们可以看到这个函数是 Θ( n )。

如果你对这一事实不确定，请记住，你总是可以通过计算指令来找到精确的复杂度。如果你愿意，现在可以尝试计算这个函数执行的实际指令，找到一个函数 f( n )，看看它确实是线性的(记住，线性意味着 Θ( n ))。

如果你对此还有疑问,或者有更多关于学业辅导方面需求的话,可以添加微信号：hmkt131联系海马课堂的Joye老师哦。