Предположим, у вас есть следующие функции 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) время?