Конспект: случаи и память

Понятия

Худший случай - максимум цены по входам размера n. Гарантия «дольше не будет», берётся по умолчанию.

Лучший случай - минимум цены. Средний - ожидание по входам (не полусумма лучшего и худшего).

Два «в среднем». Средний случай - ожидание по распределению ВХОДОВ (нужно предположение, есть плохой вход). Рандомизированное среднее - ожидание по МОНЕТКЕ алгоритма (держится на любом входе, плохого входа нет).

Вспомогательная память - память сверх входа. O(1) = «на месте», O(n) = копия. Стек рекурсии глубины d - это O(d) вспомогательной памяти.

Что унести

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

Средний считают ожиданием. У сортировки вставками лучший Θ(n), худший и средний Θ(n²) - средний рядом с худшим, а не посередине. Единую Θ пишут, только когда все случаи одного порядка.

«В среднем» двойственно. Средний случай зависит от того, каковы входы: обычный quicksort (опорный - первый) на отсортированном входе выдаёт Θ(n²). Рандомизированный (опорный случайный) - Θ(n·log n) на любом входе: плохого входа нет, только редкое невезение. Если входы бывают враждебными, случайность уводят внутрь алгоритма (случайный опорный, случайное зерно хеша).

Память сравнивают по вспомогательной (вход есть у всех). Слияние - O(n) (буфер), быстрая сортировка - O(log n) (стек), разворот на месте - O(1). Стек рекурсии - это память, даже если функция ничего не выделяет.

Время и память меняют друг на друга: хеш-таблица тратит O(n) памяти ради O(1) поиска.

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

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

Посчитал средний как (лучший + худший)/2. У среднего своё определение - ожидание; у вставок он вплотную к худшему.

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

Назвал алгоритм «на месте», забыв стек или буфер. Рекурсия глубины n - это O(n) стека, даже без единого массива; слияние - O(n) буфера.

Забыл, что копия удваивает память. На больших данных O(n) вспомогательной может не влезть - тогда решение на месте единственно возможное.

Проверь себя

Почему по умолчанию оценивают худший случай, а не средний?

Почему средний случай сортировки вставками Θ(n²), а не (n + n²)/2?

Чем средний случай (по входам) отличается от рандомизированного среднего (по монетке) и какой из них защищает от враждебного входа?

Что такое вспомогательная память и почему стек рекурсии в неё входит?

Сколько вспомогательной памяти у сортировки слиянием и у быстрой сортировки?