Что является самым недооцененным или малоизвестным, но полезным алгоритмом?

Question

Я ищу один алгоритм или структуру данных, которая настолько неизвестна, но при этом полезна, что вы считаете, что это ужасный надзор со стороны сообщества информатики или программирования. Если бы только мы все могли бы изучить эту одно, много хорошего было бы сделано для многих будущих программ.

Лучшее, что я могу придумать, это интерполяционный поиск, который знает только очень немногие программисты, тогда как все знают бинарный поиск. Я думаю, что нет никаких сомнений в том, что поиск упорядоченного списка быстро является довольно полезным и фундаментальным алгоритмом.

Эти два варианта практически идентичны для реализации - так что это не проблема.

Выполняет O (log (log (n))) на равномерно распределенных данных по сравнению с двоичными поисками O (log (n)). Это означает, что поиск 4 миллиардов номеров требует только 5 пробников против 32, это намного лучше!

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

Даже по-прежнему можно построить четный/нечетный алгоритм для чередования между ними и получить наихудший случай бинарного поиска со средним случаем интерполяционного поиска для смягчения экстремальных ситуаций.

На самом деле нет веских оснований, которые так упускают из виду большинство программистов/библиотек.

Может ли кто-нибудь еще избить это?

Answer 1

Я назначаю smoothsort. На месте, сложность времени O (n log n) наихудший случай/O (n) лучший случай.

Answer 2

trie/ternary tree ... Быстрый список префикса! Я определенно использовал их больше, чем кучи или явные структуры связанных списков (неявные связанные списки со «next» s часто полезны, хотя).

Answer 3

Другая номинация на smoothsort. Это теоретически довольно красиво и асимптотически так же хорошо, как и получается.

В случае, если вам интересно, я написал explanation о том, как работает сортировка и откуда она взята на моем личном сайте.

Кроме того, я полностью согласен с тем, что поиск интерполяции действительно потрясающий. Я рад, что кто-то еще слышал об этом. :-)