Эффективность алгоритмов сортировки

Question

Я готовлюсь к завтрашнему очень важному собеседованию, и есть одна вещь, с которой у меня большие проблемы:Алгоритмы сортировки и эффективность BigO.

Какое число важно знать?Лучшая, худшая или средняя эффективность?

Answer 1

худшее, затем среднее. знать о реальном влиянии так называемых «скрытых констант»; тоже - например, классический алгоритм быстрой сортировки имеет O (n ^ 2) в худшем случае и O (n log n) в среднем, тогда как mergesort равен O (n log n) в худшем случае, но быстрая сортировка превзойдет сортировку слиянием на практике.

Answer 2

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

Answer 3

Суммируя.

Эффективность алгоритма сортировки будет зависеть от входных данных и задачи.

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

Большинство вариантов быстрой сортировки также имеют средний случай n*log(n), но они обычно работают быстрее, чем другие не сильно оптимизированные алгоритмы.Он работает быстрее, когда он нестабилен, но стабильные варианты лишь немного медленнее.Основная проблема – худший вариант.Лучшее казуальное решение — Introsort.

Для большинства вариантов сортировки слиянием лучший, средний и худший случай зафиксирован как n*log(n).Он стабилен и относительно легко масштабируется.НО для этого требуется двоичное дерево (или его эмуляция) относительно размера общего количества элементов.Основная проблема - память.Лучшее случайное решение — тимсорт.

Алгоритмы сортировки также различаются в зависимости от размера входных данных.Я могу заявить новичку, что при вводе данных размером более 10T нет совпадения для вариантов сортировки слиянием.

Answer 4

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

Я желаю тебе удачи !! Пожалуйста, сообщите в комментарии, как все прошло!

Answer 5

Я только что закончил интервью в моем колледже ...

Каждый алгоритм имеет свои преимущества, иначе он не будет существовать. Поэтому лучше понять, что же хорошо с алгоритмом, который вы изучаете. Где это хорошо? Как это можно улучшить?

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

Всего наилучшего в вашем интервью.

Answer 6

Вы также можете рассмотреть другие типы сортировки, которые могут использоваться при определенных условиях. Например, рассмотрим сортировку Radix. http://en.wikipedia.org/wiki/Radix_sort