Модель стоимости и старший член

Коротко

Точная формула T(n) выходит громоздкой - an² + bn + c с неизвестными константами. Её огрубляют по двум причинам. Константы зависят от машины и от того, что назвали шагом, - значит несут не про алгоритм, а про железо. А из слагаемых на большом n решает только старшее: n² растёт так быстро, что bn и c рядом с ним теряются. Поэтому в ответе оставляют один старший член без множителя - «порядок роста».

Если знаешь, что считается шагом в RAM-модели и почему в оценке оставляют один старший член без константы - листай до «Теперь сам».

Как думаешь, какая быстрее

Две программы: первой нужно 100·n шагов, второй - n². Какая быстрее? Вопрос с подвохом: при n = 10 первой нужно 1000 шагов, второй - 100, второй быстрее в десять раз. А при n = 1000 первой - 100 000, второй - миллион, и теперь быстрее первая. Где-то посередине они сравнялись. Найди эту границу - и станет видно, что «быстрее» без указания размера входа ничего не значит.

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

Старший член - это как старший разряд числа. Сравнивая 3 000 000 и 90 000, ты не складываешь все цифры: у первого числа семь разрядов, у второго пять, и первое больше, что бы ни стояло в младших разрядах. В формуле T(n) роль разряда играет степень n: слагаемое с n² при большом n крупнее любого слагаемого с n, как миллионы крупнее тысяч.

Механизм 1: что честно считать шагом

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

У модели есть одна честная оговорка. Она считает арифметику над одним числом единицей - это верно, пока числа влезают в машинное слово. Над числами в тысячи цифр (криптография) сложение уже стоит длины числа, и тогда берут более тонкую модель. Для этого курса, где данные - это списки из n элементов обычного размера, единичной цены хватает; где перестанет хватать, урок скажет отдельно.

Механизм 2: почему решает старший член

Старший член - это слагаемое формулы T(n), растущее быстрее всех остальных (у 3n² + 500n + 2000 это 3n²). Пусть точный счёт дал T(n) = 3n² + 500n + 2000. Подставим растущие n:

`n`	`3n²`	`500n`	`2000`	доля `3n²`
10	300	5 000	2 000	4%
100	30 000	50 000	2 000	37%
1 000	3 000 000	500 000	2 000	86%
100 000	3·10¹⁰	5·10⁷	2 000	99,8%

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

Правило

В оценке оставляют один самый быстрорастущий член и выбрасывают множитель при нём и все младшие слагаемые. 3n² + 500n + 2000 превращается в «порядка n²». Множитель выбрасывают потому, что он про железо и про то, что назвали шагом; старший член - потому что он один и определяет рост. Формальные O, Θ и Ω для этого огрубления - в следующей главе; здесь важен сам мотив.

Разбор: где сравнялись 100n и n²

Программы из крючка равны, когда 100·n = n², то есть n = 100. До сотни элементов быстрее квадратичная (у неё меньше множитель), после сотни - линейная, и дальше разрыв только растёт: при n = 10 000 линейной нужен миллион шагов, квадратичной - сто миллионов. Вот почему порядок роста - главный ответ: он говорит, кто победит на большом входе, а на большом входе и решается, доживёт ли программа.

Разбор: когда множитель всё-таки важен

Порядок роста - первый разрез, но не последнее слово. Если два алгоритма оба линейные, но один делает 2n шагов, а другой 10n, порядок у них один, а на практике второй в пять раз медленнее - и выбор между ними идёт как раз по множителю. То же с реальными машинами: n·log n-сортировка с плохим множителем может уступать n²-сортировке на входах в десятки элементов, поэтому быстрые сортировки на маленьком куске переключаются на простую. Порядок отвечает на вопрос «что будет при большом n»; на «что быстрее прямо сейчас на моих трёхстах записях» отвечает замер.

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

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

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

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

Теперь сам

Дано T(n) = 5n² + 1000n. Каков порядок роста и при каком n слагаемое 5n² обгоняет 1000n?

Ответ. Порядок роста - n²: это старший член, множитель 5 и слагаемое 1000n отбрасываются. Обгон - там, где 5n² = 1000n, то есть 5n = 1000, n = 200. До двухсот элементов вклад 1000n больше, после - решает 5n², и дальше разрыв только растёт. Порядок роста описывает именно это «дальше», а не поведение на первых двух сотнях.

Главное

Точную T(n) = an² + bn + c огрубляют до одного старшего члена без множителя - «порядка n²». Множитель отбрасывают, потому что он про железо и про выбор шага, а не про алгоритм; младшие слагаемые - потому что старший член растёт быстрее и на большом n их подавляет (×10 к n даёт ×100 к n², но лишь ×10 к n). Шагом при этом честно считаются операции RAM-модели, цена которых не зависит от n. Порядок роста решает, кто победит на большом входе; на маленьком последнее слово за множителем и замером.