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

Question

Я только что прочитал в книге алгоритмов Кормена, что big-O и big-omega не следуют свойству трихотомии. Это означает, что для двух функций, 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)) каким-либо известным алгоритмом, то нижняя граница из P является омега (f (n)).

Answer 1

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

Answer 2

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

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

Answer 3

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

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 */ }
}

Answer 4

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

Впрочем, оно может увеличиваться до постоянной.