2
Я знаю, что это квадратичный алгоритм времени, но как он сравнивается с другими алгоритмами сортировки, такими как QuickSort или Bubble Sort?Является ли выбор подходящим алгоритмом?
A
ответ
3
Алгоритмы сортировки обычно изменяются в зависимости от характера данных, которые у вас есть.
Однако при сортировке и сортировке пузырьков легко понять (и реализовать) алгоритмы сортировки, их время выполнения - O (n^2), в худшее время, которое вы можете получить.
Что касается быстрой сортировки по аверситету, то требуется O (n log n), следовательно, это отличный вид. Однако в некоторых случаях он также может принимать O (n^2).
0
Wikipedia знает все.
Выбор сортировки в значительной степени сосет.
+0
Довольно много да, но вы можете быть более наглядными в своей критике :) –
1
Квадратичные алгоритмы времени, в зависимости от размера вашего набора данных, могут быть невероятно медленными.
п = 10e78 (о количестве атомов во Вселенной)
Для квадратичного алгоритма, это п * (10e78). Для алгоритма nlog (n), такого как quicksort или mergesort, это n * 262. Это огромная разница.
Но если ваш набор данных относительно невелик (< 1000 штук, скажем), то разница в производительности, вероятно, не будет заметна (если, разумеется, этот вид не будет повторяться повторно). В этих случаях обычно лучше использовать самый простой алгоритм и оптимизировать позже, если он окажется слишком медленным.
«Преждевременная оптимизация - это корень всего зла». -Sir Tony Hoare, популяризированный Дональдом Кнутом
+1
Это глупый пример. Никто никогда не попытается отсортировать предметы 10e78. «640K элементов должно быть достаточно для всех» - Билл Гейтс –
+0
Я согласен с первой частью вашего сообщения, но я не думаю, что выбор правильного/быстрого алгоритма сортировки является преждевременной оптимизацией. Кроме того, до тех пор, пока компоненты системы слабо связаны, алгоритм сортировки следует довольно легко заменить в более поздней оптимизации. –
+0
BTW, мне нравятся примеры с «числом атомов во вселенной», ставит все в перспективе :) –
0
Если данные, которые у вас есть, состоят только из положительных целых чисел, вы можете посмотреть на сортировку ковша. Алгоритм может иметь линейное время работы O (n) в правильных условиях.
+0
http://en.wikipedia.org/wiki/Bucket_sort –
Смежные вопросы
- 1. Является ли smartclient подходящим?
- 2. Является ли "char []" подходящим типом?
- 3. Является ли работа Кража всегда наиболее подходящим алгоритмом планирования потоков пользовательского уровня?
- 4. Является ли это известным алгоритмом упорядочения?
- 5. Является ли это признанным алгоритмом контрольной суммы?
- 6. Является ли tabu алгоритмом обучения? (CVRP)
- 7. Является ли транзакционная блокировка 2 алгоритмом сериализации?
- 8. Является ли A * лучшим алгоритмом поиска пути?
- 9. Является ли Base64 алгоритмом шифрования или кодирования?
- 10. Является ли алгоритм резания стержня полуприродным алгоритмом
- 11. Является ли это правильным алгоритмом BubbleSort?
- 12. Является ли это функциональным алгоритмом синхронизации?
- 13. Является ли F # подходящим для приложений физики?
- 14. Является ли R2RML подходящим для таблиц EAV?
- 15. Является ли шаблон декоратора подходящим выбором здесь?
- 16. Является ли Haskell подходящим для квантовых вычислений?
- 17. Является ли UINavigationController подходящим для циклов страниц?
- 18. Является ли rrdtool подходящим для анализа данных?
- 19. Является ли .length подходящим вызовом массива JavaScript?
- 20. Является ли NHibernate подходящим для применения SPC?
- 21. Является ли Django подходящим для простых webapps?
- 22. Является ли C++ подходящим для разработки Android?
- 23. Является ли SQLite подходящим для форума?
- 24. Является ли Littleproxy подходящим/готовым к выпуску?
- 25. Является ли LLVM подходящим для параллельных языков?
- 26. Является ли cakephp подходящим для корпоративного применения?
- 27. Является ли MapReduce подходящим для агрегации данных?
- 28. Является ли arduino подходящим для высокочастотного применения?
- 29. Является ли IoC подходящим для вычислительного механизма?
- 30. Является ли PriorityQueue подходящим для этого случая?
Вы всегда можете посетить все перестановки в списке и вернуть первый, который сортируется (O (n!)) :) –