Лучший, худший, средний: три вопроса к одному алгоритму

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

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

Сортировка вставками на списке [1, 2, 3, ..., n] (уже отсортирован) и на [n, ..., 3, 2, 1] (задом наперёд) - размер один, а работа? На отсортированном каждый новый элемент уже на месте, сдвигать некого. На обратном каждый элемент меньше всех левых, и его тащат в самое начало. Один вход даёт линию, другой - квадрат. Значит «сколько стоит сортировка вставками» без указания входа - вопрос без ответа.

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

Дорога до работы. В лучшем случае - пустые улицы, двадцать минут. В худшем - час пик и авария, полтора часа. В среднем - обычный день, минут сорок. Планируешь ты по худшему (выехать так, чтобы не опоздать даже в час пик), а проживаешь чаще средний. Три числа отвечают на три разных вопроса, и подменять одно другим - приходить на встречу то слишком рано, то с опозданием.

Механизм: три случая и почему главный - худший

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

• он гарантия: «дольше этого алгоритм не проработает никогда», без гаданий;
• худший вход встречается в жизни: у поиска это «элемента нет», у проверки - отказ, а именно на них система обычно и спотыкается;
• средний часто того же порядка, что худший, но требует знать, как распределены входы, - лишнее предположение, которого в гарантии нет.

Сортировка вставками по случаям: лучший - вход отсортирован, внутренний цикл не делает ни сдвига, всего n-1 проверок, Θ(n). Худший - вход обратный, на круге j сдвигов j, сумма Θ(n²). Средний - если считать, что ключ равновероятно попадает в любую из позиций левой части, в среднем он больше половины её элементов, значит сдвигается половина: tⱼ = j/2, сумма Σ j/2 = n²/4, снова Θ(n²).

Правило

Худший случай - максимум цены по входам размера n (гарантия), лучший - минимум, средний - ожидаемая цена. По умолчанию оценивают худший; лучший или средний называют явно. Средний считают ожиданием, а не как (лучший + худший)/2.

Разбор: средний - это не середина между лучшим и худшим

Соблазн посчитать средний как полусумму: лучший n, худший n², «средний» (n + n²)/2. Это бессмыслица - у среднего нет причины лежать посередине. У сортировки вставками средний считается честно: на круге j в среднем сдвигается половина префикса, tⱼ = j/2, и вся сумма 1/2 + 2/2 + ... + (n-1)/2 = n²/4. Это Θ(n²) - тот же порядок, что худший, только с вдвое меньшим множителем. Средний оказался рядом с худшим, а не в середине: полусумма дала бы примерно n²/2 и всё равно не туда. Средний - это взвешенное ожидание, и лежать он может где угодно между лучшим и худшим.

Где полусумма промахивается вопиюще: пусть алгоритм почти на всех входах делает O(1), и лишь на одном редком - O(n²). Средний тогда почти O(1): редкий вход почти ничего не весит в ожидании. А полусумма лучшего и худшего - (1 + n²)/2 ≈ n²/2, между мгновенным и квадратичным. Полусумма не знает, насколько вероятен худший вход, а среднее знает - в этом и разница.

Разбор: когда случаи одного порядка, а когда разные

У сортировки вставками лучший (n) и худший (n²) - разного порядка, поэтому единой Θ у неё нет (глава про асимптотику). А у суммы элементов списка любой вход стоит одинаково: цикл всегда проходит все n, и лучший, худший, средний - все Θ(n). Тогда пишут одну Θ(n) без оговорок. Различать случаи нужно там, где работа зависит от того, КАКОЙ вход, а не только от его размера. Если же работа определяется одним размером - как у суммы элементов, подсчёта или поиска максимума одним проходом, - все три случая совпадают, и оговорки про вход не нужны вовсе.

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

Две ошибки. Первая - выдать лучший случай за «сложность алгоритма»: «мой поиск работает за O(1)» верно лишь когда повезло с входом, а гарантия - O(n). Так меряются в рекламе, и так обжигаются в проде на первом же неудобном входе. Вторая - посчитать средний как (лучший + худший)/2: у среднего своё определение (ожидание), и он бывает вплотную к худшему, как у сортировки вставками.

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

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

Теперь сам

Линейный поиск: идём по списку, пока не встретим x. Назови лучший, худший и средний случай по порядку роста.