Модель вычислителя - за что мы платим

«Этот алгоритм делает n шагов» - фраза бессмысленная, пока не сказано, что считается шагом. Сложить два числа - шаг. А отсортировать список одной строкой a.sort() - тоже шаг? Если да, то любая задача решается за константу, надо только назвать нужную операцию элементарной.

Как думаешь, сколько шагов делает эта строка

if x in spisok:
    print("есть")

Выглядит как одно действие. На самом деле in идёт по списку слева направо и останавливается на первом совпадении. На списке из миллиона элементов, где x отсутствует, это миллион сравнений, спрятанных за двумя буквами.

Та же строка со словарём стоит один шаг: словарь считает от ключа номер ячейки и заглядывает в неё. Одна и та же запись, разница в тысячу раз, и в тексте программы её не видно.

Модель стоимости

Чтобы считать было что, нужна договорённость о том, какие операции стоят единицу. Общепринятая договорённость называется RAM-моделью: у машины есть память из пронумерованных ячеек, обращение к ячейке по номеру стоит единицу, и за единицу же считаются арифметика, сравнение, присваивание и переход. Всё остальное складывается из них.

Правило, которое из этого следует, простое: операция, объём работы которой растёт вместе с данными, единицей быть не может. Поиск по списку стоит столько элементов, сколько просмотрел. Склейка двух списков стоит их суммарную длину. Сортировка стоит n·log n сравнений. Машина курса считает шаги именно так, поэтому её счётчик не расходится с рассуждением на бумаге.

Логарифм в цене сортировки - тот самый счётчик делений пополам из главы «Математика и логика для курса»: log₂ n это сколько раз n делится на 2 до единицы. Стоит в оценке именно он, потому что быстрые алгоритмы на каждом шаге отбрасывают половину данных. Ещё раз он понадобится в главе про остановку цикла, на числе кругов алгоритма Евклида.

Считаем вместе: два способа посчитать уникальные

Задача: сколько различных чисел в списке из n элементов. Первый способ:

unikalnye = []
for x in a:
    if x not in unikalnye:
        unikalnye.append(x)
print(len(unikalnye))

Внешний цикл делает n кругов. На каждом круге not in проходит по списку unikalnye, а он растёт. Если все числа разные, суммарно получится 0 + 1 + 2 + ... + (n-1), то есть примерно n²/2 сравнений. При n = 10 000 это пятьдесят миллионов.

Второй способ:

vidennye = set()
for x in a:
    vidennye.add(x)
print(len(vidennye))

Проверка принадлежности множеству стоит один шаг независимо от размера множества. Получается n шагов вместо n²/2 - при тех же десяти тысячах элементов десять тысяч операций против пятидесяти миллионов. Разница не в аккуратности записи, а в том, за что платит каждая строка.

Считаем вместе: цена снятия из начала

ochered = [1, 2, 3, 4, 5]
pervyj = ochered.pop(0)

pop(0) возвращает первый элемент, а потом сдвигает все остальные на одну ячейку влево - иначе нарушится главное свойство массива, из-за которого обращение по номеру стоит единицу. Значит снятие из начала стоит n, а снятие с конца (pop()) - единицу, там двигать нечего.

Отсюда следует практический вывод, который пригодится в разделе про очереди: очередь (кто раньше встал, тот раньше обслужен) на списке с pop(0) обрабатывает n элементов за n²/2 операций. Очередь, которая помнит номер головы и не двигает хвост, справляется за n.

Чего модель не видит

RAM-модель считает все обращения к памяти одинаковыми. Настоящая машина - нет: данные, лежащие подряд, читаются в разы быстрее разбросанных, потому что попадают в кеш процессора. Поэтому обход массива обгоняет обход связного списка при одинаковом порядке роста. Модель врёт здесь сознательно: она ловит порядок роста, а не константу, и для выбора между n² и n·log n этого достаточно. Разговор про константы и кеш будет в разделе про структуры на практике.

Теперь сам

Сколько шагов сделает этот фрагмент на списке из n элементов?

itog = ""
for slovo in slova:
    itog = itog + slovo