Изучаю книгу Кормена, параллельно изучая Java. Там хорошо описаны алгоритмы, но такой вопрос по ним. Есть кучу сортировок, поиска нужных элементов и пр. Вопрос: как понять, какой именно алгоритм использовать в ситуации, если у них у всех время T примерно одинаково и находится в зазоре O(N) <= t <= O(N^2)? Самому графики составлять и время замерять?
-
3` время T примерно одинаково и находится в зазоре` ну ничего себе вывод... Вы поняли, что такое асимптотическая сложность?– MBo4 июл 2020 в 3:36
-
199.9% времени программист использует стандартные алгоритмы и структуры данных. Чтобы понять, что конкретно применять в этих 99.9% случаях, достаточно разобраться в стандартных структурах данных и временем их работы. Чтобы решать нетривиальные задачи, которые составляют 0.01% от всех задач, надо не только хорошо знать теорию (можете начать с книги Стивена Скиены - Алгоритмы. Руководство по разработке), но и прорешать пару-тройку тысяч задач на практике.– tym321674 июл 2020 в 3:51
-
А знание всяких динамических, фиббоначиевых куч надобно в Java?– Александр Скворцов4 июл 2020 в 10:53
-
Знаю, что такое асимптотика. Да, алгоритмы, имеющие ограниченную сверху сложность O(N^2), могут сильно разниться, например, T(N) = N^2 - N + 1 и T(N) = N^2. Просто я уже хотел в OriginPro графики строить, ведь еще время зависит и от изначальной упорядоченности элементов– Александр Скворцов4 июл 2020 в 10:55
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, иногда слиянием (для случая, когда нужна стабильная сортировка).
-
Вот прямо сейчас сижу и пытаюсь по Кормену разобрать mergeSort. Как я понимаю, я должен их, во-первых, знать, а во-вторых, знать, когда их применить, в какой ситуации и почему. Сортировка слиянием вроде использует много дополнительной памяти. Я тут уже создавал тему, хотел бы на Java писать серверные приложения, поэтому думаю, что без алгоритмов будет тяжко. 4 июл 2020 в 18:26
-
1Достаточно знать общие принципы,а не досконально реализацию. Отметьте для себя - довольно быстрая, без худшего случая, стабильная, требует памяти. Обратите только внимание на используемую в mergesort процедуру merge слияния сортированных массивов, это может пригодиться.– MBo4 июл 2020 в 18:32
-
Да, свойства важные. Я смотрю на общее решение в КОрмене и пытаюсь сам код воспроизвести(в серых табличках у него) на Java, но пока не идет. Я, как понимаю, должен знать свойства алгоритмов, которые Вы назвали. 4 июл 2020 в 18:58
-
1
-
1Ну вот стоят две колонны солдат по росту, нужно создать общую по росту. Просто на каждом шаге выбираете более высокого бойца и отправляете в новую колонну.– MBo5 июл 2020 в 2:22