Нет простого способа доказать, что любой данный алгоритм является асимптотически оптимальным.
Доказательство оптимальности (если когда-либо) иногда следует через годы и / или десятилетия после написания алгоритма. Классический пример - структура данных Union-Find / disjoint-set .
Леса с непересекающимися наборами - это структура данных, в которой каждый набор представлен древовидной структурой данных, в которой каждый узел содержит ссылку на свой родительский узел. Впервые они были описаны Бернардом А. Галлером и Майклом Дж. Фишером в 1964 г., хотя их точный анализ занял годы.
[...] Эти две техники дополняют друг друга; При совместном использовании амортизированное время на операцию составляет всего O(α(n)), где α(n) - это обратная функция f(n) = A(n,n), а A - чрезвычайно быстро растущая функция Ackermann.
[...] Фактически, это асимптотически оптимально: Фредман и Сакс показали в 1989 году, что слова Ω (α (n)) должны быть доступны для любой структуры данных с несвязным множеством на операцию в среднем.
Для некоторых алгоритмов оптимальность может быть доказана после очень тщательного анализа, но, вообще говоря, нет простого способа определить, является ли алгоритм оптимальным после его написания. На самом деле, не всегда легко доказать, является ли алгоритм даже правильным.
Смотри также
- Википедия / Матричное умножение
- Википедия / Асимптотически оптимальная
Это открытая проблема, являются ли многие из самых известных алгоритмов сегодня асимптотически оптимальными или нет. Например, существует алгоритм O(nα(n)) для поиска минимальных остовных деревьев. Является ли этот алгоритм асимптотически оптимальным, неизвестно, и, скорее всего, он будет признан значительным результатом, если он будет решен в любом случае.
Практические соображения
Обратите внимание, что иногда асимптотически «худшие» алгоритмы лучше на практике из-за многих факторов (например, простота реализации, фактически лучшая производительность для данного диапазона входных параметров и т. Д.).
Типичным примером является быстрая сортировка с простым круговым выбором, который может демонстрировать квадратичную производительность в худшем случае, но все еще предпочтителен во многих сценариях по сравнению с более сложным вариантом и / или другими асимптотически оптимальными алгоритмами сортировки.