7
Какие все алгоритмы вы находите с удивительным (жестким, странным) анализом сложности с точки зрения обоих - Результирующая нотация и уникальность в том, как они анализируются?Алгоритмы для анализа больших O
A
ответ
2
1
Недетерминистически полиномиальная сложность получает мой голос, особенно с (по общему признанию, маловероятной) возможностью, что она может оказаться такой же, как полином. В том же духе все, что теоретически может выиграть от квантовых вычислений (N.B., этот набор - далеко не все алгоритмы).
Другой, который получит мой голос, будет обычным математическим операциям на числах произвольной точности - здесь вы должны учитывать такие вещи, как умножение больших чисел, дороже, чем умножение малых. В Кнуте довольно много анализов (что никому не должно быть новостью). Метод Карацубы довольно опрятен: вырезать два фактора пополам (A1; A2) (B1; B2) и размножать A1 B1, A1 B2, A2 B1, A2 B2 отдельно, а затем объединить результаты. Recurse при желании ...
+0
Метод Карацубы отличный, это правда. Однако, поскольку быстрое преобразование Фурье выполняет свертку, его можно использовать для выполнения самых быстрых размножений, считая, что числа достаточно велики, чтобы оправдать обострение записи смешанного формата БПФ и его настройку. –
+0
Хмм, мне придется это посмотреть. Насколько точны компоненты, чтобы гарантировать точное целочисленное умножение? – Edmund
+0
Как я понимаю, вам просто нужна достаточная точность для хранения последнего номера. Хотя метод умножения БПФ можно также использовать для целых типов напрямую, и всегда даются точные ответы. У меня нет моей копии Кнута, но я думаю, что он упоминает технику и перебирает ее. –
2
Это одно простое, но расческа Сортировка немного раздувает мой разум.
http://en.wikipedia.org/wiki/Comb_sort
Это такой простой алгоритм, по большей части она читается как чрезмерно сложной пузырьковой сортировки, но это O (N * Log [п]). Я нахожу это слегка впечатляющим.
Множество алгоритмов для быстрых преобразований Фурье также впечатляет, математика, которая доказывает, что их действительность триптична, было очень интересно попытаться доказать некоторые из моих собственных.
http://en.wikipedia.org/wiki/Fast_Fourier_transform
Я могу довольно легко понять простые десятичный, несколько премьера десятичного и алгоритмы смешанного Radix, но тот, который работает на наборах, размер которых являются простым довольно прохладно.
15
У меня есть (вполне) несколько примеров:
- Структура union-find данных, которая поддерживает операции в (амортизируется) обратного Ackermann времени. Это особенно приятно, потому что структуру данных невероятно легко кодировать.
- Splay trees, которые являются самобалансирующимися двоичными деревьями (то есть никакая дополнительная информация не хранится иначе, чем BST - нет красной/черной информации. Amortized analysis был по существу изобретен, чтобы доказать границы для деревьев в виде пауз, деревья распускаются в амортизируются логарифмического времени, но в худшем случае линейное время. доказательства остыли.
- Fibonacci heaps, которые выполняют большинство операций очередей приоритетов в амортизационном постоянная время, таким образом улучшая время выполнения Dijkstra's algorithm и других проблем. Как и с расширяющимися деревами, там являются гладкими «потенциальными функциями».
- Алгоритм Бернарда Шазелле для вычисления минимальных остовных деревьев в линейном временном обратном Ack ermann время. Алгоритм использует soft heaps, вариант традиционного priority queue, за исключением того, что может произойти некоторая «коррупция», и на запросы могут не ответить правильно.
- В то время как на тему MST: оптимальный алгоритм был given by Pettie and Ramachandran, но мы не знаем время работы!
- Множество рандомизированных алгоритмов заинтересовало анализы.Я упомянул только один пример: триангуляция Делоне может быть вычислена в ожидаемое время O (n log n) на incrementally adding points; анализ, по-видимому, сложный, хотя я этого не видел.
- Алгоритмы, которые используют «бит-трюки», могут быть аккуратными, например. sorting in O(n log log n) время (и линейное пространство) - это правильно, он разбивает барьер O (n log n), используя больше, чем просто сравнения.
- Cache-oblivious algorithms часто имеют интересные анализы. Например, cache-oblivious priority queues (см. Стр. 3) используют log log n уровней размеров n, n 2/3, n 4/9 и так далее.
- (Статический) диапазон - минимальные запросы на массивы аккуратные. standard proof проверяет ваши ограничения в отношении сокращения: минимально минимальные запросы уменьшаются до наименее общего предка в деревьях, что в свою очередь сводится к минимально-минимальным запросам в определенном типах массивов. На последнем этапе также используется симпатичный трюк.
2
2D упорядоченный анализ поиска весьма интересен. У вас есть двумерный числовой массив чисел NxN, где каждая строка сортируется влево-вправо, и каждый столбец сортируется сверху вниз. Задача состоит в том, чтобы найти определенное число в массиве.
Рекурсивный алгоритм: выберите элемент в середине, сравните с целевым номером, отбросьте четверть массива (в зависимости от результата сравнения), примените рекурсивно к остальным 3 кварталам, довольно интересно проанализировать.
0
Shell sort. Существует множество вариантов с различными приращениями, большинство из которых не имеют преимуществ, кроме как сделать complexity analysis simpler.
Это алгоритм? – shoosh
@p Этот ответ, вероятно, прекрасен, хотя это только ссылка. «Функция Аккермана» достаточно, чтобы найти ее в Интернете, и вопрос, который, вероятно, не соответствует теме, - это только вымогательство алгоритмов, а не объяснений. – royhowie