Какой термин описывает алгоритм, который имеет ту же сложность, что и основная проблема?

Question

Несколько месяцев назад, исследуя структуры данных для проекта, я наткнулся на термин, который мне очень понравился, и который можно использовать следующим образом:

Этот [Алгоритм / Решение / Структура данных] является оптимальным для всех

Это означает, что временная (или пространственная, в зависимости от контекста) сложность решения, на которое делается ссылка, равна фундаментальной сложности и решаемой им проблеме.

Например, если мы проигнорируем квантовые вычисления и примем, что проблема сортировки составляет O(n log n) время в общем случае, то в отношении сортировки кучи со сложностью по времени все-оптимально, поскольку ее сложность также O(n log n), тогда как пузырьковая сортировка не является оптимальной для всех, поскольку O(n^2) хуже, чем O(n log n).

Понятия не имею, где я это прочитал, до сих пор мне не удалось найти его в Google, и я не могу вспомнить, что это беспокоило меня с тех пор!

Answer 1

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

Если было доказано, что задача принимает хотя бы f (x), она называется Omega (f (x)); наихудший случай алгоритма - big-O (g (x)). Когда f (x) == g (x), то есть наихудший случай для решения является лучшим случаем для задачи, алгоритм имеет большое значение тета (f (x)). Таким образом, heapsort, например это тета (n * log (n)).

Answer 2

Возможно, вы говорите о Асимптотически оптимальном алгоритме :

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