Как оценить сложность по коду

Оценка кода делается в четыре шага.

1. Назвать N. Длина списка, длина строки, величина числа – размер входа надо проговорить явно, иначе оценка ни о чём.
2. Посмотреть на циклы и вложенность. Один цикл по всем элементам – $O(N)$, цикл в цикле – $O(N^2)$.
3. Проверить, как меняется переменная цикла. Растёт на единицу – N шагов; умножается или делится на 2 – $O(\log N)$ шагов.
4. Поискать скрытые циклы. Самая частая ошибка – принять короткую запись за одно действие.

nums = [4, 8, 15, 16, 23, 42]

# один цикл: N проходов
total = 0
for x in nums:
    total = total + x
print(total)   # 108

# два цикла подряд: N + N = 2N проходов, всё ещё O(N)
biggest = nums[0]
for x in nums:
    if x > biggest:
        biggest = x
count = 0
for x in nums:
    if x == biggest:
        count = count + 1
print(biggest, count)   # 42 1

# цикл в цикле: N · N проходов, O(N²)
total = 0
for x in nums:
    for y in nums:
        total = total + x * y
print(total)   # 11664

Проверим на задаче «есть ли в списке два одинаковых числа». Прямой способ – сравнить каждый элемент с каждым, но пару незачем проверять дважды: если сравнили a[0] и a[3], обратная пара ничего нового не даст. Поэтому внутренний цикл начинают сразу после текущего элемента.

for i in range(len(a)):
    for j in range(i + 1, len(a)):
        if a[i] == a[j]:
            print('есть')

Сравнений выходит $N \cdot (N-1)/2$: для 100 элементов – 4950, для 1000 – 499 500. Это вдвое меньше полного перебора, но 1/2 – постоянный множитель, а его O-нотация отбрасывает. Класс остаётся $O(N^2)$.

Цена знакомых операций. a – список длины N, s – строка длины N, st – множество, d – словарь.

Практических вывода два. Список удобно наращивать с конца: append от длины не зависит, а insert(0, x) каждый раз двигает весь список. И проверку «есть ли элемент» в цикле делают по множеству: тогда она стоит $O(1)$ вместо $O(N)$.

Сначала определите сложность каждого фрагмента сами. Списки a и b – длины N.

# фрагмент 1
total = 0
for x in a:
    total = total + x * x
print(total)

# фрагмент 2
for x in a:
    print(x)
for x in a:
    print(x * 2)

# фрагмент 3
for x in a:
    if x in b:
        print(x)

# фрагмент 4
n = 1000000
count = 0
while n > 1:
    n = n // 2
    count = count + 1
print(count)

Разбор.

1. $O(N)$. Один проход по списку; три действия внутри – постоянный множитель.
2. $O(N)$. Циклы идут последовательно: N + N = 2N, двойка отбрасывается.
3. $O(N^2)$. Явный цикл один, но x in b – скрытый перебор второго списка на каждом шаге.
4. $O(\log N)$. N здесь – само число, а не длина списка. Оно уменьшается вдвое, поэтому шагов примерно $\log_2(1\,000\,000) \approx 20$.

Если b сделать множеством, третий фрагмент станет $O(N)$: проверка x in b будет стоить $O(1)$.

Оценку полезно проверить замером. Всё нужное лежит в стандартной библиотеке.

from time import perf_counter

start = perf_counter()

total = 0
for i in range(1, 1000001):
    total = total + i

finish = perf_counter()
print('время:', finish - start, 'с')

Берут perf_counter(), а не time(): шаг time() на Windows около 0,016 с, и настенные часы могут подводиться.

Метод удвоения – запустить алгоритм на данных размера N, потом 2N, потом 4N и посмотреть, во сколько раз каждый раз вырастает время.

Вот что показали часы на двух знакомых алгоритмах.

Сумма циклом:

Перебор пар:

В первой таблице двойки, во второй четвёрки – ровно то, что дала оценка по коду без всякого запуска.

Замер находит и то, чего не видно в коде. Собрать список из N элементов можно через append и через insert(0, x). По таблице операций первая стоит $O(1)$, вторая – $O(N)$.

Время append при удвоении N растёт примерно вдвое. Время insert растёт вчетверо: 0,56, 2,25, 9,05. Значит, весь цикл стоит $O(N^2)$, хотя цикл в нём один и вложенности не видно: второй проход спрятан внутри insert.

Три правила честного замера:

• брать N такой, чтобы время было хотя бы десятые доли секунды;
• не ставить print и input между start и finish;
• делать 3–5 запусков и брать минимум: помехи могут только замедлить замер.