使用 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）....暗示它是θ（n！我可以得到一些帮助吗？
这是一个递归函数，因此根据定义，第 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）。