Пример немонотонной сложности худшего случая

Question

Кто-нибудь знает о естественной программе или алгоритме, который имеет немонотонное худшее поведение?

По немонотонному наихудшему поведению я имею в виду, что существует натуральное число n, так что наихудшее время выполнения для входов размера n + 1 меньше, чем наихудшее время выполнения для входов размера n.

Конечно, легко создать программу с таким поведением. Возможно, это произойдет и при малых n (например, n = 1) в естественных программах. Но меня интересует полезный алгоритм, который не монотонен для больших n.

Answer 1

Является ли кто-нибудь осведомленным о естественной программе или алгоритме, который имеет немонотонное худшее поведение ?

Укажите «естественная программа или алгоритм». Понятие «алгоритм» имеет определение, о котором я знаю, и, безусловно, есть алгоритмы (как вы правильно признаете), которые имеют немонотонную наихудшую сложность выполнения. Является ли программа «естественной», если она не делает ненужной работы или имеет минимальную сложность выполнения для класса проблемы, которую она решает? В таком случае, можно ли утверждать, что BubbleSort не является алгоритмом? Что еще более важно, я могу определить проблему, наиболее эффективное решение которой имеет немонотонное худшее поведение. Будет ли такая проблема «неестественной»? Каково ваше определение «естественной проблемы»?

Конечно, легко создать программу с таким поведением.

Тогда какой вопрос? Пока вы не посвятите себя определению естественных/полезных алгоритмов и проблем, ваш вопрос не отвечает. Вас интересуют только ранее существовавшие алгоритмы, которые люди уже используют в реальном мире? Если это так, вы должны сказать это, и проблема становится одной из поисков литературы. Честно говоря, я не могу представить себе разумное определение «естественного, полезного алгоритм», который бы исключить множество примеров алгоритмов с немонотонной сложностью исполнения ...

Но я заинтересован в качестве полезного алгоритма, который не- монотонно для большой n.

Укажите «полезный алгоритм». Понятие «алгоритм» имеет определение, о котором я знаю, и, безусловно, есть алгоритмы (как вы правильно признаете), которые имеют немонотонную наихудшую сложность выполнения. Является ли алгоритм «полезным», если он правильно решает какую-то проблему? Я могу легко определить проблему, которая может быть решена с помощью алгоритма с немонотонной сложностью выполнения.

Answer 2

Подумайте о бинарном поиске.

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

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

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

Обратите внимание, что все это зависит от реализации, и поэтому не может быть реального ответа без реального алгоритма (и, кроме того, реальной реализации).

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