8

我到处搜索，似乎找不到很多与运行时复杂性、递归和 java 相关的材料。

我目前正在我的算法课中学习运行时复杂性和 Big-O 表示法，并且在分析递归算法时遇到了麻烦。

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

这是一种递归方法，它将简单地遍历双向链表并打印出元素。

我唯一能想到的是它的运行时复杂度为 O(n)，因为递归方法调用的数量将取决于 DList 中的节点数量，但我仍然觉得不舒服这个答案。

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

或者我只是完全偏离轨道并且运行时复杂性是恒定的，因为它所做的只是DNodes从DList?

4

5 回答 5

3

乍一看，这看起来像是尾递归模 cons的经典案例，尾调用的泛化。它相当于一个带有迭代次数的循环。

然而，事情并没有那么简单：这里的棘手之处在于d.getElement()对一个不断增长的字符串进行加法：这本身就是一个线性运算，并且会重复N多次。因此，您的功能的复杂性是O(N^2)。

于 2012-03-02T21:48:46.740 回答
2

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

  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)。

于 2012-03-02T21:49:08.940 回答
2

这是一个非常简单的示例，但诀窍是定义递归关系，它是给定输入大小的运行时间函数，就较小的输入大小而言。对于此示例，假设在每个步骤中完成的工作花费恒定的时间 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)。这个例子并不是特别有趣，但是如果你看一下合并排序的运行时间或其他分而治之的算法，你可以更好地了解递归关系。

于 2012-03-02T21:57:05.110 回答
0

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

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

（假设函数getElement在恒定时间内运行。）这个方程的解通常是 T(n) = O(n)。

这是一般情况。但是，有时您可以在不编写此类方程式的情况下分析算法。在这个例子中，你可以很容易地争论每个元素最多被访问一次，并且每次都完成一些固定时间的工作；因此，完成这项工作需要 O(n) 。

于 2012-03-04T18:34:42.860 回答
0

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

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

于 2012-03-02T21:48:41.987 回答