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

Question

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

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

Answer 1

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

Answer 2

Короче.

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

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

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

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

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

Answer 3

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

Answer 4

Я закончил с одним собеседованием в моем колледже только сейчас ...

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

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

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

Answer 5

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

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

Answer 6

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