Функция суммирует значения односвязного списка длины n, читая элементы «по индексу», как в массиве. Определите время её выполнения.
Сумма через чтение по индексу
Код
class Node:
def __init__(self, value: int, next: "Node | None" = None) -> None:
self.value = value
self.next = next
def get(head: Node, index: int) -> int:
node = head
for _ in range(index):
node = node.next
return node.value
def total(head: Node, n: int) -> int:
result = 0
for i in range(n):
result += get(head, i)
return resultКакое время выполнения?
Ответ: O(n²)
get(head, i) каждый раз идёт от головы и делает i шагов. Всего 0 + 1 + … + (n − 1) = n(n − 1)/2 шагов. Константы отбрасываются — O(n²). Для массива тот же код работал бы за O(n): чтение по индексу там O(1). А по связанному списку правильно идти один раз: node = node.next.
- Подсказка 1
Сколько шагов делает get(head, i) для конкретного i?
- Подсказка 2
Сложите шаги для i = 0, 1, …, n − 1. Похожую сумму вы видели в разборе сортировки выбором.