Считаем точно: от кода к формуле T(n)

Если умеешь считать T(n) построчно и знаешь, что тест цикла выполняется на раз чаще тела - листай до «Теперь сам».

Как думаешь, сколько раз выполнится проверка

i = 0
while i < n:
    i = i + 1

Тело цикла выполнится n раз - это видно сразу. А сколько раз выполнится сама проверка i < n? Не n, а n + 1: последний раз она срабатывает, когда i уже дорос до n, возвращает ложь и выпускает из цикла. Один лишний раз - мелочь для этого примера, но именно на нём чаще всего ошибаются в точном счёте, а из таких мелочей и собирается формула.

На что это похоже

Счёт времени - это чек из магазина. В строке чека две колонки: цена за штуку и количество. Итог - не длина чека и не число позиций, а сумма произведений по всем строкам. Программа - тот же чек: у каждой строки кода своя цена (сколько шагов она стоит за одно выполнение) и своё количество (сколько раз выполнилась). T(n) - это итог по чеку.

Механизм: цена, число выполнений, сумма

Каждой строке приписывают цену c - число шагов за одно выполнение. Для строк из RAM-модели (арифметика, сравнение, присваивание, обращение по индексу) цена - константа: она не зависит от n. Дальше считают число выполнений каждой строки на входе размера n. T(n) - сумма произведений цены на число выполнений по всем строкам.

Возьмём сумму элементов списка:

s = 0                    # c1, один раз
for i in range(n):       # c2, n+1 раз (последняя проверка - вхолостую)
    s = s + a[i]         # c3, n раз
print(s)                 # c4, один раз

Складываем произведения:

T(n) = c1·1 + c2·(n+1) + c3·n + c4·1
     = (c2 + c3)·n + (c1 + c2 + c4)

Получилась функция вида a·n + b - линейная. Все c - неизвестные константы, но их точные значения не нужны: важно, что при них n стоит в первой степени (то есть просто n, а не n·n = n²) - чем выше степень, тем круче растёт время. Это и есть ответ на вопрос «как растёт время»: вдвое больше данных - вдвое больше шагов.

Правило

T(n) - сумма по всем строкам произведения «цена строки × число её выполнений». Цена строки из RAM-модели - константа. Тело цикла выполняется столько раз, сколько кругов; проверка условия - на один раз больше тела.

Разбор: цикл с досрочным выходом

for i in range(n):
    if a[i] == x:
        print(i)
        break

Сколько шагов? Зависит от того, где стоит x. Если он первый - тело отработает один раз и break оборвёт цикл: константа. Если x в списке нет - тело отработает n раз: линия. Одна и та же программа даёт разный счёт на входах одного размера. Пока запомни сам факт; отдельная глава про худший и лучший случай разбирает, какой из этих счётов берут за ответ.

Разбор: та самая лишняя проверка

Вернёмся к разнице «тело против проверки». Посчитаем строку while в поиске минимума:

m = a[0]                 # 1 раз
i = 1                    # 1 раз
while i < n:             # n раз
    if a[i] < m:         # n-1 раз
        m = a[i]
    i = i + 1            # n-1 раз

Тело крутится n-1 раз (от i=1 до i=n-1), а проверка i < n - n раз: на единицу больше, последний прогон отправляет из цикла. В сумме это меняет только свободный член b, а не множитель при n, - но в точном счёте писать надо честно, иначе на вложенных циклах ошибка на единицу превратится в ошибку в целом слагаемом.

Что ломается без этого

Наивный счёт «одна строка - один шаг» ломается на строках, которые сами прячут цикл. if x in spisok - это не одна цена, а проход по списку, и в чеке у неё стоит не 1, а до n. Посчитав такую строку за единицу, ты объявишь квадратичную программу линейной и удивишься, почему она стоит на боевых данных (эту ловушку разбирал раздел про модель вычислителя). Поэтому цена строки - это не «строка», а работа, которую строка делает.

Зачем это в работе

T(n) считают до запуска, чтобы узнать, доживёт ли код до боевого объёма. Машина курса печатает не только результат, но и число шагов и таблицу роста: данных втрое - шагов втрое (линия) или вдевятеро (квадрат). Так формула с бумаги сверяется с замером, и расхождение сразу видно - обычно это спрятанный за коротким синтаксисом цикл.

Теперь сам

Посчитай T(n) для фрагмента (списки a и b длины n):

for i in range(n):
    for j in range(n):
        print(a[i] + b[j])