Алгоритмы для анализа Big O

Question

Какие все алгоритмы, по вашему мнению, имеют удивительный (сложный, странный) анализ сложности с точки зрения как - результирующей нотации O, так и уникальности их анализа?

Answer 1

У меня есть (довольно) несколько примеров:

• Структура данных union-find , которая поддерживает операции в (амортизированном) обратном аккерманном времени. Это особенно приятно, потому что структура данных невероятно легко закодировать.
• Сплайновые деревья , которые являются самобалансирующимися бинарными деревьями (т. Е. Никакая дополнительная информация не сохраняется, кроме BST - никакой красной / черной информации). Придумано, чтобы доказать границы для splay-деревьев, splay-деревья работают за амортизированное логарифмическое время, но наихудшее линейное время. Доказательства классные.
• Кучи Фибоначчи , которые выполняют большинство операций с приоритетной очередью в амортизированном постоянном времени, улучшая тем самым время выполнения алгоритма Дейкстры и другие проблемы. Как и в случае с деревьями сплайнов, есть отличные доказательства «потенциальной функции».
• Алгоритм Бернара Шазеля для вычисления минимальных остовных деревьев в линейное время, обратное аккерманскому времени. Алгоритм использует soft heaps , вариант традиционной очереди приоритетов , за исключением того, что может произойти некоторое "повреждение" и запросы могут не отвечать правильно.
• Хотя по теме MST: оптимальный алгоритм был дан Петти и Рамачандраном , но мы не знаем время работы!
• Многие рандомизированные алгоритмы имеют интересный анализ. Я приведу только один пример: триангуляция Делоне может быть вычислена за ожидаемое время O (n log n) путем постепенного добавления точек ; анализ, по-видимому, сложен, хотя я его не видел.
• Алгоритмы, использующие «хитрости в битах», могут быть аккуратными, например, сортировка по O (n log n) по времени (и линейному пространству) - это верно, он преодолевает барьер O (n log n), используя больше, чем просто сравнения.
• Кэш-забывающие алгоритмы часто имеют интересные анализы. Например, очереди кэширования без учета приоритетов (см. Стр. 3) используют журнал регистрации n уровней размеров n, n ^2/3 , n ^4/9 , и так далее.
• (Статические) минимальные по диапазону запросы к массивам аккуратны. Стандартное доказательство проверяет ваши пределы в отношении сокращения: запросы с минимальным диапазоном сводятся к наименьшему предку в деревьях, что, в свою очередь, сводится к запросам с минимальным диапазоном в конкретном виде массивов. На последнем этапе также используется симпатичный трюк.

Answer 2

2D упорядоченный поисковый анализ довольно интересен. У вас есть двумерный числовой массив чисел NxN, где каждая строка сортируется слева направо, а каждый столбец сортируется сверху вниз. Задача - найти конкретное число в массиве.

Рекурсивный алгоритм: выбрать элемент посередине, сравнить с целевым числом, отбросить четверть массива (в зависимости от результата сравнения), применить рекурсивно к оставшимся 3 четвертям, что довольно интересно анализировать.

Answer 3

Это довольно просто, но Comb Bort немного поражает меня.

http://en.wikipedia.org/wiki/Comb_sort

Это такой простой алгоритм, который по большей части читается как слишком сложная пузырьковая сортировка, но это O (n * Log [n]). Я нахожу это слегка впечатляющим.

Множество алгоритмов быстрых преобразований Фурье тоже впечатляют, математика, доказывающая их обоснованность, является триповой, и было забавно попытаться доказать некоторые из них самостоятельно.

http://en.wikipedia.org/wiki/Fast_Fourier_transform

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

Answer 4

функция Аккермана .

Answer 5

Недетерминированная полиномиальная сложность получает мой голос, особенно с возможностью (по общему признанию маловероятной), что она может оказаться такой же, как и полиномиальная. В том же духе все, что теоретически может выиграть от квантовых вычислений (N.B. этот набор далеко не все алгоритмы).

Другой способ получить мой голос - это обычные математические операции с числами произвольной точности - здесь нужно учитывать, что умножение больших чисел обходится дороже, чем умножение маленьких. Это довольно много анализа этого в Кнуте (который не должен быть новостью для всех). Метод Карацубы довольно аккуратный: разделите два фактора пополам на цифру (A1; A2) (B1; B2) и умножьте A1 B1, A1 B2, A2 B1, A2 B2 по отдельности, а затем объедините результаты. Повторяйте при желании ...

Answer 6

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