Возможно ли, что временная сложность любого алгоритма уменьшается по мере увеличения размера ввода, в любом примере

Я только что прочитал в книге алгоритмов Кормена, что большие-O и большие-омега не следуют за свойством трихотомии. Это означает, что для двух функций f(n) и g(n) может быть выполнено не f(n) = O(g(n)) и f(n) = Omega(g(n)). В примере они утверждают, что если функция n^(1+sin n), чем это возможно.

Хотя верно, что в реальном мире алгоритм может иметь время выполнения чего-то вроде sin n. Так как это иногда уменьшалось, с увеличением размера ввода. Кто-нибудь знает какой-либо такой алгоритм или может дать небольшой фрагмент кода, который делает это.

Спасибо за ответы, поэтому в этом случае правильно предположить, что Учитывая задачу P с размером n, если она не может быть решена в O (f (n)) временем любым известным алгоритмом, то нижняя граница of P является Omega (f (n)).

Ответ 1

У меня возникают трудности с пониманием значимой проблемы с уменьшением сложности. "Осмысленной" проблеме нужно будет прочитать или коснуться частей всего своего ввода. Если вход не кодируется очень неэффективно, обработка его должна занимать все большее количество времени.

Он может увеличиваться в сторону константы.

Ответ 2

Алгоритм строчного поиска Boyer-Moore становится быстрее, когда искомая строка увеличивается. Конечно, ограничивающий фактор чаще всего представляет собой длину строки, в которую вы искали.

Ответ 3

Среднее время работы SAT для произвольно генерируемых предложений 3CNF в конечном итоге уменьшается с увеличением отношения предложений к переменным. Интуиция заключается в том, что, когда имеется очень много предложений относительно числа переменных, более вероятно, что формула "явно" неудовлетворительна; то есть типичные алгоритмы SAT-решения (шаг или два лучше, чем исчерпывающий поиск, но достаточно простой, чтобы охватить в рамках логического курса), быстро достигают противоречий и останавливаются.

Конечно, это экспериментальные наблюдения для некоторого понятия "случайных" формул 3CNF. Я не уверен, что люди доказали об этом.

Ответ 4

Используйте любую обратную функцию.

f(x) -> 1 / x
f(x) -> 1 / x²
f(x) -> 1 / log(x)

По мере роста входа x результирующее значение будет уменьшаться. Достаточно просто связать меньшее значение с меньшим числом шагов в алгоритме. Просто используйте счетчик в цикле, чтобы перейти к этому номеру.

Вот простой алгоритм.

function(x) {
    step = 0.001
    y = 1 / x;
    for (i = 0; i < y; i += step) { /* do something awesome here */ }
}