java - 递归算法的运行时复杂性

Question

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

我目前正在我的算法课上学习运行时复杂性和大 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 检索元素？

Answer 1

乍一看，这像是tail recursion modulo cons的经典案例，尾调用的概括。相当于一个有迭代次数的循环。

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