python - 2个不同的附加函数到链表的时间复杂度？
问题描述
假设您有以下 Python 函数并假设链表的正常结构：
def append(self, element): # Line 1
new_node = Node(element, None) #2nd arg. is the next_node # Line 2
ptr = self.head # Line 3
if self.size == 0: # No elements case # Line 4
self.head = new_node # Line 5
self.tail = new_node # Line 6
self.size += 1 # Line 7
else: # 1 or more elements # Line 8
while ptr.next_node != None: # Line 9
ptr = ptr.next_node # Line 10
ptr.next_node = new_node # Line 11
self.tail = new_node # Line 12
self.size += 1 # Line 13
该函数尝试将节点附加到链表的末尾，同时更新相关值。我想知道函数的时间复杂度——理想情况下，它是 O(c)，其中 c 是一个常数，但我相信它是 O(n)。
逐行分析，我可以看到第 1-7 行和第 10-13 行在每个函数调用中执行一次，并且在恒定时间内运行。然而，第 8-10 行将在线性时间内运行，因为 while 循环必须为 n 个节点执行 n 次。此外，第 10 行也被执行了 n 次。
我是否正确地认为该函数在 O(n) 时间内运行？
接下来，考虑一个替代函数。
def append(self, element): # Line 1
new_node = Node(element, None) #2nd arg. is the next_node # Line 2
ptr = self.tail # Line 3
if self.size == 0: # No elements case # Line 4
self.head = new_node # Line 5
self.tail = new_node # Line 6
self.size += 1 # Line 7
else: # 1 or more elements # Line 8
ptr.next_node = new_node # Line 9
self.tail = new_node # Line 10
self.size += 1 # Line 11
第 1-11 行都是 if 语句或赋值，它们在恒定时间内运行，并且每次函数调用都执行一次。因此，此函数将以 O(c) 运行。
它会在 O(c) 时间内运行吗？