Пример алгоритма, где член младшего порядка доминирует во время выполнения для любого практического ввода?

Обозначение Big-O скрывает постоянные коэффициенты, поэтому существуют некоторые алгоритмы , которые недопустимы для любого разумного размера входных данных, потому что коэффициент по члену очень велик.$O(n)$$n$

Существуют ли какие-либо известные алгоритмы, для которых время выполнения равно но с некоторым членом младшего разряда, который настолько велик, что для разумных размеров входных данных он полностью доминирует во время выполнения? Я хотел бы использовать алгоритм, подобный этому, в качестве примера в курсе алгоритмов, поскольку он дает вескую причину, почему нотация big-O не является чем-то вечным.o ( f ( n ) $O(f(n))$$o(f(n))$

Спасибо!

Криптография - пример, если вырожденный. Например, нарушение шифрования AES - это - все, что вам нужно сделать, - это найти правильный ключ среди конечного числа, 2 128 или 2 192 или 2 256, в зависимости от размера ключа (предположим, что достаточно открытого текста известно определить ключ однозначно). Однако даже 2 128 операций заняли бы сегодня все компьютеры (миллиард или около того, каждый из которых выполняет около миллиарда операций за один раз) больше, чем время жизни вселенной (около миллиарда миллиардов секунд).$O(1)$$2^{128}$$2^{192}$$2^{256}$$2^{128}$

Немного другой способ проиллюстрировать, почему big-O - это еще не все, это отметить, что мы иногда используем другой алгоритм для небольших входных размеров. Например, взять быструю сортировку. При правильном выборе пивота (что сложно!) Это . Quicksort работает по принципу «разделяй и властвуй»: каждый случай требует много сортировки небольших массивов. Для небольших массивов квадратичные методы, такие как сортировка вставок, работают лучше. Таким образом, для лучшей производительности быстрая сортировка большого массива включает в себя множество прогонов сортировки вставки для небольших размеров.$O(n \lg n)$

Два примера приходят на ум из области параметризованной сложности и алгоритмов FPT. Это может быть не совсем то, что вы ищете, но здесь идет.

Рассмотрим проблему с графом, такую ​​как 3-ЦВЕТ или ЦИКЛ. Обе проблемы могут быть выражены в монадической логике второго порядка, и, следовательно, могут быть решены в линейном времени графов с ограниченной шириной дерева. Это результат Bruno Courcelle , но полученный алгоритм далеко не практичен.

$O(p^{9p/2})L$$O(p^{2p}L)$$p$$L$

Отчасти с вашим вопросом связаны алгоритмы, которые, как известно, теоретически имеют хорошую производительность, но не используются в реальных задачах из-за непрактичности в небольших случаях. Другими словами, как вы и просили, «заявленная производительность» возможна только для больших входов в теории, а не в практических приложениях. это иногда отражается в оценках Big-Oh, в других случаях не совсем так. некоторые алгоритмы имеют хорошую теоретическую «производительность», но очень логически сложны и никогда не были реализованы кем-либо, и поэтому «производительность» на практических размерах экземпляров даже не известна, например, как с проблемой максимального потока .

• тестирование простоты в P с помощью алгоритма AKS

• Алгоритм умножения матрицы Копперсмита-Винограда

• см. также практичны ли современные алгоритмы максимального потока? tcs.se

• см. также мощные алгоритмы, слишком сложные для реализации tcs.se

• галактические алгоритмы RJLipton блог

Это шутка, но есть серьезная сторона ...

$O(n\log n)$$O(n^2)$