Как бы вы, где один алгоритм предпочтительнее, чем другой алгоритм

Question

Я пытаюсь сравнить два алгоритма и их эффективность. Я пытаюсь найти значение для n, где один алгоритм становится более эффективным, чем другой алгоритм. Любые полезные примеры или ресурсы будут огромной помощью.

Answer 1

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

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

Эмпирическое профилирование производительности - это инструмент, который нужно использовать при работе с высокочастотными, повторяющимися проблемами, которые обычно связаны с небольшими затратами *

(*) То, что составляет небольшие входные данные, зависит от сложности используемых алгоритмов. Например, для задачи коммивояжера ввод размера 5 мал, а ввод размера 15 огромен. Для сортировки 20 элементов будут считаться маленькими, 20000 большими и 2000000 будут огромными.