Один проход по данным
O(n) означает линейное время: объём работы растёт вместе с входными данными. Вдвое больше элементов — вдвое больше шагов.
В Python линейное время обычно выглядит как один цикл for по списку или словарю. Любой алгоритм, которому нужно хотя бы посмотреть на каждый элемент — суммирование, подсчёт, поиск в неотсортированном списке, — не может быть быстрее O(n).
Линейная сложность — это хорошо. Миллионы элементов не проблема для одного прохода.
Линейный поиск
Если список не отсортирован, единственный способ найти значение — проверять элементы по одному, с самого начала. Это и есть линейный поиск.
В худшем случае — значение стоит последним или его нет вовсе — цикл проходит все n элементов. Именно этот худший случай и описывает O(n).
Найти значение и его позицию
Цикл проверяет "one", "two", "three", прежде чем дойти до "four", — 4 шага для совпадения по индексу 3. break останавливает цикл, как только значение найдено.
Вывод: полная программа на Python
words = ["one", "two", "three", "four", "five"]
steps = 0
for i, w in enumerate(words):
steps += 1
if w == "four":
print("найдено по индексу", i, "за", steps, "шага")
break
Обход каждого элемента
Многие повседневные задачи — это один проход по всему списку: сложить все значения, запоминать самое большое из встреченных, подсчитать элементы, прошедшие проверку. Каждый элемент обрабатывается ровно один раз, поэтому все они имеют сложность O(n).
Два или три таких прохода подряд — это по-прежнему линейное время: O(2n) и O(3n) сводятся к O(n).
Сумма всех элементов
Цикл прибавляет каждый элемент к total. 8 элементов — 8 сложений: классическая форма одного прохода.
Вывод: полная программа на Python
nums = [3, 1, 4, 1, 5, 9, 2, 6]
total = 0
for n in nums:
total += n
print("сумма", len(nums), "элементов:", total)
Найти наибольшее значение
biggest сначала равно первому элементу; каждый следующий элемент, который больше, заменяет его. После одного прохода остаётся наибольшее значение — 9.
Вывод: полная программа на Python
nums = [3, 1, 4, 1, 5, 9, 2, 6]
biggest = nums[0]
for n in nums[1:]:
if n > biggest:
biggest = n
print("наибольшее значение:", biggest)
Подсчитать совпадения
Цикл проверяет каждое слово условием len(w) > 3 и считает попадания. Три слова длиннее 3 букв.
Вывод: полная программа на Python
words = ["one", "two", "three", "four", "five"]
count = 0
for w in words:
if len(w) > 3:
count += 1
print(count, "слова длиннее 3 букв")