Как выбирать алгоритмы по эффективности в разных ситуациях?
Изучаю книгу Кормена, параллельно изучая Java. Там хорошо описаны алгоритмы, но такой вопрос по ним. Есть кучу сортировок, поиска нужных элементов и пр. Вопрос: как понять, какой именно алгоритм использовать в ситуации, если у них у всех время T примерно одинаково и находится в зазоре O(N) <= t <= O(N^2)? Самому графики составлять и время замерять?
Ответы (1 шт):
в зазоре O(N) <= t <= O(N^2) - пропасть огромного размера.
Если линейные и O(nlogn) алгоритмы обычно пригодны для обработки данных любого размера, то квадратичные - только для ограниченных размеров (для сортировок это десятки и сотни элементов).
Можете посчитать, сколько понадобится времени на выполнение сортировки, если имеется N элементов (10, 100, 1000, 10000 и т.д.), одна операция занимает, скажем, 1 наносекунду (10^-9 c), при количествe операций a*N, a*N*log(N), a*N^2, где коэффициент a поварьируйте (например, логлинейный возьмите с a=100, а квадратичный с a=5)
Про изначальную упорядоченность - это относится как к лучшему и худшему случаю (в таблице ниже), так и к "натуральному поведению" - например, вставки быстро работают на почти упорядоченных данных, teamsort, или natural mergesort, а обычному mergesort - пофиг.
В английской вики есть таблица сравнения алгоритмов сортировки, так что можно подобрать по конкретной ситуации.
Например если требуется сортировать десятки элементов - хорошо подойдёт сортировка вставками. Если при этом сами элементы большие по размеру - выбором, т.к. у неё меньше обменов, перемещения данных.
В большинстве случаев стоит выбирать сортировку, встроенную в стандартную библиотеку используемого языка - обычно это быстрая сортировка или teamsort, иногда слиянием (для случая, когда нужна стабильная сортировка).