Я только что прочитал в книге алгоритмов Кормена, что большие-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)).
У меня возникают трудности с пониманием значимой проблемы с уменьшением сложности. "Осмысленной" проблеме нужно будет прочитать или коснуться частей всего своего ввода. Если вход не кодируется очень неэффективно, обработка его должна занимать все большее количество времени.
Он может увеличиваться в сторону константы.
Алгоритм строчного поиска Boyer-Moore становится быстрее, когда искомая строка увеличивается. Конечно, ограничивающий фактор чаще всего представляет собой длину строки, в которую вы искали.
Среднее время работы SAT для произвольно генерируемых предложений 3CNF в конечном итоге уменьшается с увеличением отношения предложений к переменным. Интуиция заключается в том, что, когда имеется очень много предложений относительно числа переменных, более вероятно, что формула "явно" неудовлетворительна; то есть типичные алгоритмы SAT-решения (шаг или два лучше, чем исчерпывающий поиск, но достаточно простой, чтобы охватить в рамках логического курса), быстро достигают противоречий и останавливаются.
Конечно, это экспериментальные наблюдения для некоторого понятия "случайных" формул 3CNF. Я не уверен, что люди доказали об этом.
Используйте любую обратную функцию.
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 */ }
}