Как мы можем модифицировать почти любой алгоритм, чтобы иметь хорошее время работы в лучшем случае?

Это вопрос из " Введения в алгоритмы " Кормена и др., Но это не домашнее задание. Вместо этого это самообучение.

Я много думал и искал в Google. Ответ, который я могу придумать:

Используйте другой алгоритм.
Дайте ему лучшие примеры
Используйте лучший компьютер для запуска алгоритма

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

Итак, как мы можем изменить почти любой алгоритм, чтобы иметь хорошее время выполнения в лучшем случае?

Ответ 1

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

Например, для любого типа вы можете сделать лучший случай O(n), проверив, отсортирован ли массив, а если он есть, верните его как есть.

Обратите внимание, что это не влияет на средние или худшие случаи (при условии, что они не лучше, чем O(n)), и вы в основном улучшаете алгоритм наилучшей сложности времени.

Примечание. Если размер ввода ограничен, такая же оптимизация делает наилучший случай O(1), так как чтение ввода в этом случае равно O(1).

Ответ 2

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

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

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

Ответ 3

Мы можем изменить алгоритм, чтобы иметь наилучшее время работы:

Если алгоритм находится в точке его цели/решения, для ex, для возрастающего сорта, он уже сортируется по возрастанию и т.д.

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

Ответ 4

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

Ответ 5

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

Вот как мы можем добиться хорошего времени выполнения в лучшем случае.