递归算法的运行时复杂度

Question

我搜索了很多资料，似乎找不到关于运行时复杂度、递归和Java相关的内容。

我正在学习算法课程中的运行时复杂度和大O符号，并且我在分析递归算法方面遇到了困难。

private String toStringRec(DNode d)
{
   if (d == trailer)
      return "";
   else
      return d.getElement() + toStringRec(d.getNext());
}

这是一个递归方法，简单地遍历双向链表并打印出其中的元素。

唯一能想到的是，它的时间复杂度为 O(n)，因为递归方法调用的次数将取决于DList中节点的数量，但我仍然不确定这个答案是否正确。

我不确定是否应该考虑 d 和 d.getNext() 的添加。

或者我完全走错了，运行时间复杂度是恒定的，因为它只是从 DList 中检索 DNodes 中的元素？

- Jimmie J

---

请参见：https://dev59.com/LUjSa4cB1Zd3GeqPFGzD - dyoo

Answer 1

乍一看，这似乎是一个经典的尾递归模余cons案例，它是尾调用的一般化。 它相当于循环迭代次数。

然而，事情并不那么简单：这里的棘手之处在于将d.getElement()添加到增长的字符串中：这本身就是一个线性操作，并且重复N次。 因此，您的函数的复杂度为O(N^2)。

- Sergey Kalinichenko

---

嗯，我以为 d.getElement() 是用来获取节点 d 中存储的数据。我想他需要更清楚地表达他的问题... - XiaoChuan Yu

@XiaoChuanYu 不，d.getElement() 是 O(1)。后面的字符串拼接才是线性的。 - Sergey Kalinichenko

是的，感谢您没有忽略字符串拼接的成本。这完全正确。高斯求和1+2+...+n发挥了作用，这就是二次方程式的来源。 - dyoo

Answer 2

如果T(n)是在调用n个元素的列表上执行toStringRec时执行的基本操作数量（在这种情况下 - 当我们进入函数体时，任何内部行最多只执行一次，并且除第二个返回之外的所有内容都不是O(1)），那么

  T(0) = 1  - as the only things that happen is the branch instruction and a
              return
  T(n) = n + T(n-1) for n > 0 - as the stuff which is being done in the
              function besides calling toStringRec is some constant time stuff and
              concatenating strings that takes O(n) time; and we also run
              toStringRec(d.getNet()) which takes T(n-1) time

现在我们已经描述了算法的复杂性。我们可以计算出T的闭式形式，T(n) = O(n**2)。

- Adrian Panasiuk

---

不，函数中的“完成工作”不是O(1)。假设每个元素中字符串的大小非空，这是需要花费与n成比例时间的工作。因此，T(n)的闭合形式看起来像T(n) = 1C + 2C + 3C + ... + nC，其中C是某个常数。这是一个高斯和。T(n)是二次的，而不是线性的。 - dyoo

Answer 3

这是一个相当简单的例子，但关键在于定义循环递归关系，它是关于较小输入大小的运行时函数。对于这个例子，假设每个步骤所做的工作花费恒定的时间C，并且假设基本情况不做任何工作，则可以表示为：

T(0) = 0
T(n) = C + T(n-1)

您可以使用代入法解出一个序列，从而求解运行时间：

T(n) = C + T(n-1) = 2C + T(n-2) = 3C + T(n-3) = ... = nC + T(n-n) = nC + 0 = nC

根据O的定义，这个方程是O(n)。这个例子并不特别有趣，但如果你看一下归并排序或其他分治算法的运行时间，你就可以更好地理解递推关系。

- cjm

---

当然，在这个例子中，你也可以用常识来理解：你正在打印链表中的每个节点，因此你执行的打印次数与列表的大小以完全相同的速度增长。因此，它是线性时间。 - cjm

在这个特定的例子中，我们不能假设每个步骤所花费的时间是恒定的，因为Java中的字符串连接方式不同。 - dyoo

我认为这个假设是可以的，因为这个问题的重点不在于查找Java库函数的复杂度，而在于理解这种递归算法如何被一般性地分析。 - cjm

我认为制定递归公式是解决这个问题的关键。但是：我们需要确保我们正在解决正确的递归公式。如果我们实际运行此程序并绘制其在n范围内的行为，我们将观察到O(n^2)时间。这需要一个解释，否则我们的分析就没有用了。递归必须修改为T(n) = C*n + T(n-1)，因为字符串连接的原始操作与被连接的字符串的大小成线性关系。除非语言提供字符串绳索，否则我们必须处理字符串上+的非常数成本。 - dyoo

好的，非常感谢你向我介绍了字符串绳，我之前还没有听说过。 - cjm

Answer 4

正如您所建议的，该算法的运行时间复杂度为O(n)。您的列表中有n个项目，对于每个项目，算法将执行几乎固定数量的工作（即元素和下一个访问，加上新的toStringRec调用）。从DNode检索元素需要恒定的时间，在大O符号中舍弃恒定的时间。

关于递归方法（在大多数情况下），有趣的是它们的空间复杂度也是O(n)。每次调用toStringRec时都会创建一个新的堆栈条目（用于存储传递给方法的参数），这将被调用n次。

- sgmorrison

---

很遗憾，这种解释给出了错误的结论。它没有考虑字符串连接的成本。也就是说，在每个项目上的成本不是恒定的。这是这个问题的一个重要点。请更正此错误。 - dyoo

我同意每个项目的成本不是恒定的，但我不同意它是O(n)。string1 + string2的成本是O(m)，其中m是结果字符串的长度。具体来说，连接两个字符串最坏的情况是创建一个长度为m的新char[]，并逐个从原始字符串复制每个字符。在给定代码的第n次迭代时，toStringRec可能会返回一个非常长的字符串，但连接的成本仍然是O(m)。在这个例子中，m与n没有直接联系，因为getElement可能返回空字符串或非常长的字符串。 - sgmorrison

假设存在某个长度 m，它是任何特定 d.getElement() 大小的上限。那么我们从 toStringRec(node) 得到的返回字符串的大小受到以 node 开始的链的长度的限制。令 T(n) 为计算成本。则：对于一些常数 C1、C2、C3，有 T(n) < C1 + C2 * m * (n-1) + C3 * T(n-1)。中间项表示字符串连接。让 C4 是一个比 C1 大且也是 m * C2 的倍数的常数。 - dyoo

抱歉，证明很长。必须分开。:) 无论如何，现在我们说 T(n) < C1 + C2 * m * (n-1) + C3 * T(n-1) < C4 + C2 * m * (n-1) + C3 * T(n-1)。由于我们选择了C4是C2 * m的倍数，我们进行因式分解。我们现在可以说对于某个C，T(n) < C2 * m * (n + C) + C3 * T(n-1)。术语C2 * m也是一个常数。所以我们真正拥有的是类似于T(n) < C1 * n + C2 + C3 * T(n-1)的东西。开始展开递归。我们最终得到T(n) < C1 * (1 + 2 + ... + n) + C2，其中C1和C2是一些常数。(1 + 2 + ... + n)被广泛认为是高斯求和，其闭合形式为n(n+1)/2。完成！ - dyoo

如果您还有疑问，请提出问题。一旦您确认无误，可以相应地编辑您的答案。祝你好运！ - dyoo

Answer 5

对于这样的递归算法，通常可以编写递归方程来计算顺序。一般习惯用T(n)表示执行的指令数。在这个例子中，我们有：

T(n) = T(n - 1) + O(1)

（假设函数getElement运行时间为常数）。这个方程的解是显然的，T(n) = O(n)。

那是一般情况。但有时候你可以不用编写这样的方程来分析算法。在这个例子中，可以轻易地证明每个元素最多被访问一次，且每次执行的工作都是常数级别的；因此完成任务所需的总时间为O(n)。

- MMS