Правила обращения: множители, слагаемые, вложенность

Если знаешь правила «сумма = максимум», «множитель долой», «вложенность = произведение» и лестницу порядков - листай до «Теперь сам».

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

T(n) = 3n² + 500n + 2000 мы объявили Θ(n²). Чтобы это сделать, пришлось выбросить сразу три вещи: множитель 3, слагаемое 500n и слагаемое 2000. Но выбрасывали не наугад - за каждым выбросом стоит правило, выведенное из определения O и Θ. Их всего три, и, зная их, порядок читаешь с одного взгляда, не расписывая c и n₀ каждый раз.

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

Это как значащие цифры в физике. Складывая 3 000 000 и 500, ты не пишешь 3 000 500 - ты пишешь 3 000 000, потому что второе слагаемое ниже точности. Правила асимптотики говорят ровно, что здесь «ниже точности»: множитель и всё, что растёт медленнее старшего. Не небрежность, а договорённость об уровне огрубления.

Механизм: три правила и откуда они

Множитель-константа выбрасывается: c·f(n) = Θ(f(n)). По определению Θ нужны c₁ и c₂, зажимающие c·f вокруг f; годятся c₁ = c₂ = c. Множитель уходит внутрь констант определения - его для того и завели.

Сумма равна старшему слагаемому: f(n) + g(n) = Θ(max(f, g)). Пусть f растёт не медленнее g. Снизу f + g ≥ f = max. Сверху f + g ≤ f + f = 2·max. Значит сумма зажата между 1·max и 2·max - это и есть Θ(max). Поэтому 3n² + 500n это Θ(n²): старшее слагаемое съедает младшее.

Независимая вложенность перемножается. Если внешний цикл делает a(n) кругов, а на каждом внутренний - b(n), и b(n) не зависит от того, где сейчас внешний, всего кругов a(n)·b(n). Два цикла по n дают n²; цикл n с внутренним log n - n·log n.

Лестница порядков

Эти классы надо узнавать в лицо, от медленного роста к быстрому:

1  <  log n  <  n  <  n·log n  <  n²  <  n³  <  2ⁿ  <  n!

Каждый растёт быстрее предыдущего - и вот почему именно так:

• log n - сколько раз n делить пополам до единицы (из раздела про завершаемость). Удваивание входа добавляет к log n всего единицу: рост еле заметный.
• n - один проход: сколько данных, столько работы.
• n·log n - n проходов, но каждый вложен в деление пополам; типичная цена хороших сортировок.
• n², n³ - все пары, все тройки элементов: каждый вложенный проход добавляет множитель n.
• 2ⁿ - все подмножества n элементов (подмножество - любой выбор части из них: хоть пустой, хоть все целиком). Каждый новый элемент можно взять или не взять, поэтому вариантов вдвое больше на каждый +1 к n. Это уже не множитель, а удвоение - при n = 60 вариантов больше, чем атомов в комнате.
• n! - все перестановки n элементов (перестановка - способ расставить их по порядку). Первый элемент выбираем n способами, второй - n-1, и так до одного; их произведение и записывают знаком факториала: n! = n·(n-1)·...·1. Растёт быстрее любой экспоненты.

Граница между n³ и 2ⁿ - это граница между «медленно, но выполнимо» и «невыполнимо». В записи степени числа различают основание и показатель: у n³ основание - это n (что возводят), показатель - 3 (в какую степень); у 2ⁿ наоборот - основание 2, показатель n. У n³ с ростом входа растёт основание, у 2ⁿ - показатель, и показатель в итоге бьёт основание: 2ⁿ перегонит любую nᵏ с каким угодно фиксированным k.

Правило

Множитель-константу выбрасывай; сумму заменяй старшим слагаемым; независимые вложенные циклы перемножай. Порядок фрагмента читается по лестнице: найди самую дорогую часть - она и задаёт класс.

Разбор: читаем сложность по частям

for x in a:            # n раз
    print(x)           # блок 1: n
for i in range(n):     # n раз
    for j in range(n): # блок 2: n·n = n²
        rabota()
s = a[0] + a[-1]       # блок 3: константа

Три независимых куска: n, n², константа. По правилу суммы берём максимум - n². Первый цикл и обращение по индексу теряются рядом с двойным циклом. Итог - Θ(n²), и это видно без единого c.

Разбор: где сумма НЕ схлопывается в один множитель

Правило суммы берёт максимум, а не складывает порядки - это разные вещи. n² + n² это Θ(n²), а не Θ(n⁴): складываются функции, а перемножаются - только вложенные циклы. И наоборот, два цикла ПОДРЯД (не вложенные) дают сумму, а не произведение: n плюс n это Θ(n), а не Θ(n²). Множитель n добавляет именно ВЛОЖЕННОСТЬ - когда внутренний цикл прокручивается целиком на каждом круге внешнего.

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

Три типовые ошибки. Сложить порядки вместо взятия максимума: увидеть n + n² и написать n³. Перемножить непрерывные куски: два цикла подряд принять за n². И недооценить экспоненту: 2ⁿ на глаз кажется «немного больше n²», а на самом деле при n = 50 это уже квадриллион - разница между «посчитается» и «не досчитается никогда». Лестница порядков и спасает от последнего: 2ⁿ стоит правее n³ не зря.

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

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

Теперь сам

Назови порядок роста, применяя правила:

for i in range(n):
    for j in range(n):
        rabota()
for k in range(n):
    rabota()
print(n)