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

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

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


performance algorithm big-o theory
person MedicineMan    schedule 13.09.2009    source источник
comment
Я очень надеюсь, что ваш завтрашний интервьюер не будет НАСТОЛЬКО завсегдатаем :)   -  person DVK    schedule 13.09.2009
comment
Я не знаю, что плохого в том, чтобы задавать вопросы, чтобы улучшить ваши общие знания. Особенно при подготовке к интервью вы должны атаковать свои самые слабые стороны, не обращая внимания на лицо или то, насколько глупо вы можете выглядеть. По моему опыту, те, кто больше всего боится показаться дураком, испытали наименьший личностный рост.   -  person MedicineMan    schedule 13.09.2009

Ответы (6)


arrow_upward
4
arrow_downward

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

person Martin DeMello    schedule 13.09.2009
comment
Естественная сортировка слиянием может оставить быструю и быструю сортировку далеко позади -- cfr svn.python .org/projects/python/trunk/Objects/listsort.txt, stackoverflow.com/questions/154504/, hatfulofhollow.com/posts/code/timsort и т. д. и т. д. - person Alex Martelli; 13.09.2009
comment
Хотя это отличный ответ, я должен сказать, что я бы не решился нанять кого-то, кто не понимает чего-то такого простого и очевидного, как разработчик. - person DVK; 13.09.2009
comment
ДВК, ты говоришь как парень из башни из слоновой кости, человек, который ревностно охраняет свою маленькую область знаний с величайшим усилием. Разве вы здесь не для того, чтобы поделиться своими знаниями и своими усилиями по поддержке сообщества? Вы опасаетесь, что кто-то приобретет компетенцию в этой области, а затем займет вашу работу? - person MedicineMan; 13.09.2009
comment
Алекс: это довольно аккуратно. не знал, насколько хорош timsort. - person Martin DeMello; 13.09.2009
comment
@Врач. Ваш ответ @DVK был слишком оборонительным. Есть несколько хороших компаний, которые полностью согласны с ДВК - это Paint The Fence. - person jamesh; 14.09.2009

arrow_upward
2
arrow_downward

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

person Ed Marty    schedule 13.09.2009

arrow_upward
2
arrow_downward

Короче.

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

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

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

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

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

person Margus    schedule 13.09.2009
comment
Ответ не касается основного опубликованного вопроса, но он дает ценную информацию о различных характеристиках сортировки, основанную на реальном опыте. - person MedicineMan; 13.09.2009

arrow_upward
1
arrow_downward

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

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

person San Jacinto    schedule 13.09.2009
comment
спасибо, запоминание никогда не бывает лучшим путем, но когда я сталкиваюсь с крайним сроком, мне нужно расставить приоритеты в том, что происходит в мозгу в первую очередь. - person MedicineMan; 13.09.2009

arrow_upward
1
arrow_downward

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

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

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

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

person Lazer    schedule 14.09.2009

arrow_upward
0
arrow_downward

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

person ldog    schedule 14.09.2009