Обозначение Big-O: улучшение и смена алгоритма

Улучшение O(n)

Глядя на некоторые кривые, нельзя не задать вопрос: можем ли мы улучшить данный код, может быть даже перевести его в более быстрый класс Big-O?

Смена алгоритма

Если алгоритм, который ты пытаешься улучшить, является одним из хорошо известных и хорошо изученных алгоритмов, шансы найти эквивалентный, но неизвестный алгоритм в лучшем классе сложности примерно равны нулю. Если ты найдешь его, твой уровень — «Бог» :)

Если, с другой стороны, ты смотришь на какой-то паршивый самодельный код, быстро собранный во время восстановления после тяжелого похмелья, то шансы не так уж плохи.

Стоит предварительно обрабатывать входные данные. В некоторых случаях временная сложность может быть улучшена путем переупорядочивания входных данных.

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

Хороший алгоритм сортировки требует времени O(n*log(n)), но сокращает время каждого последующего поиска с O(n) до O(log(n)). Или для всех n поисков от O(n^2) до O(n*log(n)). Большая победа!

Также стоит изменять структуру данных. Иногда полезно проверить, как хранятся ваши входные данные.

Пример: вставка нового значения в отсортированный линейный список требует O(n) времени, так как все значения после вновь вставленного должны быть смещены на одну ячейку.

(Обратите внимание, что здесь речь идет о среднем времени. В отдельных случаях эти операции могут производиться быстрее. Например, если новое значение вставлено в конце, то сдвигать нечего.)

Ты можешь указать, что поиск правильного места для вставки также занимает некоторое время и для отсортированного линейного списка это было бы O(log(n)) при использовании бинарного поиска, поэтому точная формула будет O(n + log(n)). Однако, как мы видели в разделе «Упрощение термина», достаточно использовать наиболее влиятельную часть сложности алгоритма. В данном сценарии это сложность от n.

Если ты вставляешь новые данные очень часто, лучше превратить этот список в сбалансированное дерево. Тогда вставка нового значения требует только O(log(n)) времени. (Помни, что log(n)  примерно равен высоте сбалансированного бинарного дерева).