Конспект: счёт операций

Понятия

T(n) - время алгоритма как функция от размера входа, измеренное в шагах, а не в секундах. Секунды зависят от машины, число шагов - нет.

Цена строки - число шагов за одно её выполнение. Для операций RAM-модели (арифметика, сравнение, присваивание, обращение по индексу) - константа.

Число выполнений - сколько раз строка отработала на входе размера n. Тело цикла - по разу на круг; проверка условия - на раз больше.

Треугольная сумма - 1 + 2 + ... + n = n(n+1)/2, порядка половины n². Возникает у вложенного цикла с растущей внутренней границей.

Старший член (порядок роста) - самый быстрорастущий член формулы без множителя. 3n² + 500n + 2000 → порядка n².

Что унести

T(n) считают построчно: цена строки, умноженная на число её выполнений, сложить по всем строкам. s = c1·1 + c2·(n+1) + ....

Проверка цикла выполняется на один раз больше тела - последний, холостой раз и завершает цикл. В точном счёте это отдельное слагаемое.

Вложенный цикл с растущей границей даёт СУММУ 1 + 2 + ... + n = n(n+1)/2, а не произведение n·n. Деление на 2 - из приёма «сложить ряд с собой задом наперёд». Отсюда n²/2 у сортировки вставками в худшем случае и у перебора пар.

В ответе оставляют один старший член без множителя. Множитель отбрасывают - он про железо и выбор шага; младшие слагаемые - старший их подавляет (×10 к n даёт ×100 к n², но лишь ×10 к n).

Шагом честно считается операция RAM-модели, чья цена не зависит от n. Операция, объём работы которой растёт с данными, шагом быть не может.

Порядок роста снимают с живой программы по таблице роста: ×2 данных → ×2 шагов (линия), ×4 (квадрат), чуть больше чем ×2 (n·log n).

Ловушки джокера

Посчитал строки вместо работы. if x in spisok - это проход по списку, до n шагов, а не один. Цена строки - её работа, и квадрат прячется без единого вложенного for.

Решил, что два цикла - это всегда n². Константный внутренний цикл (range(10)) или ранний break оставляют время линейным. Квадрат даёт растущая вместе с n внутренняя граница, а не глубина отступа.

Забыл про лишнюю проверку. Тело крутится n раз, проверка условия - n+1. На вложенных циклах ошибка на единицу превращается в ошибку в целом слагаемом.

Выбрал алгоритм по одному порядку на маленьком входе. До точки пересечения решает множитель: n² с малым множителем обгоняет n·log n на входах в десятки элементов. Порядок отвечает про большой вход, замер - про текущий.

Спутал порядок с секундами. Число шагов - свойство алгоритма и входа; секунды - железа и языка. Порядок роста сравнивают в шагах.

Проверь себя

Как из кода получить T(n) построчно, и почему проверка цикла даёт n+1, а не n?

Откуда у вложенного цикла берётся n²/2 и почему именно /2, а не целый n²?

Почему в оценке оставляют только старший член и выбрасывают множитель?

Как по таблице роста отличить линию от квадрата, не читая код?

Всегда ли два вложенных цикла квадратичны? Приведи контрпример.