递归算法的运行时复杂性

Question

我搜索过高和低,似乎找不到很多与运行时复杂性,递归和java相关的资料.

我目前正在学习Algorithms类中的运行时复杂性和Big-O表示法,而且我在分析递归算法时遇到了麻烦.

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

这是一个递归方法,它将简单地迭代一个双向链表并打印出元素.

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

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

还是我只是完全偏离轨道和运行时间复杂度为常数,因为它做的事就从检索的元素DNodes在DList？

Answer 1

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

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