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

Question

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

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

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