python - 在 Python 中递归地反转链表的运行时大 O 表示法

Question

使用 ADT 链接列表和以下代码，我将如何用 Big O 表示法表示运行时？：

def reverse (self):
 (1)if self._head is not None:
      (2)temp = self._head.item
      (3)self._head = self._head.next
      (4)self.reverse()
      (5)self.append(temp)

我的思考过程：第 1 - 3 行基本上是不变的，因为它们只是从链接列表的开头设置和获取项目，第 5 行根据定义是 theta(n)。每次列表变小，所以我认为函数运行 n(n-1)(n-2).... 暗示它是 theta(n!)。我能得到一些帮助吗？

Answer 1

这是一个递归函数，因此根据定义，第 4 行不是 theta(n)。

这实际上将在 O(n) 中运行。

基本上这个函数的复杂性是：

T(n) = T(n - 1) + O(1) // T(n - 1) 用于对列表进行递归调用，一个元素较短，其他操作为常数。

为了解决这个问题，我们使用归纳法：

T(n) = n * O(1) + T(0) = n * O(1) + O(1) = O(n)

对于追加，确实在最坏的情况下它可能是 O(n)，但摊销的最坏情况是 O(1)。