Завтра я изучаю довольно важное интервью, и есть одна вещь, с которой у меня возникают большие проблемы: алгоритмы сортировки и эффективность BigO.Эффективность алгоритмов сортировки
Какое число важно знать? Лучшая, худшая или средняя эффективность?
худший, а затем средний. быть в курсе реального воздействия так называемых «скрытых констант», например, классический алгоритм быстрой сортировки - это O (n^2) в худшем случае и O (n log n) в среднем, тогда как mergesort является O (n log n) в худшем случае, но quicksort на практике превосходит слияние.
Природный Mergesort может оставлять quicksort и quickersort в пыли - cfr http://svn.python.org/projects/python/trunk/Objects/listsort.txt, http://stackoverflow.com/questions/154504/is- timsort-general-purpose-or-python-specific, http://www.hatfulofhollow.com/posts/code/timsort/ и т. д. и т. д. –
Хотя это отличный ответ, я должен администратор, я бы колебался нанимать кого-то, кто не понимал чего-то столь элементарного и очевидного, как разработчика. – DVK
DVK, вы похожи на башню из слоновой кости, такого человека, который ревниво защищает свою небольшую область знаний с наибольшим усилием. Вы не можете поделиться своими знаниями и своими усилиями по поддержке сообщества? Вы боитесь, что кто-то получит компетенцию в этой области, а затем возьмет вашу работу? – MedicineMan
Все они важны, чтобы знать, конечно. Вы должны понимать, что преимущества одного алгоритма сортировки в среднем случае могут стать ужасным дефицитом в худшем случае, или худший случай не так уж плох, но лучший случай не так уж хорош, и он работает только хорошо несортированные данные и т. д.
Я рекомендую вам не просто запоминать эти фактоиды. Узнайте, почему они такие, какие они есть. Если бы я брал интервью у вас, я бы не стал задавать вопросы, которые показывают, что вы понимаете, как анализировать алгоритм, а не просто отбрасывать то, что вы видели на веб-странице или в книге. Кроме того, за день до собеседования не время заниматься этим.
Желаю вам удачи! Пожалуйста, сообщите в комментарии, как это было!
спасибо, запоминание никогда не лучший маршрут, но когда вы сталкиваетесь с крайним сроком, мне нужно определить приоритеты, что происходит в мозгу в первую очередь. – MedicineMan
Вкратце.
Эффективность алгоритма сортировки зависит от входных данных и задачи.
большинство быстрых вариантов сортировки имеет свой средний случай тоже п * журнал (п), но твой, как правило, быстрее, чем другие не сильно оптимизированные алгоритмы. Это быстрее, когда оно нестабильно, но стабильные варианты лишь на несколько меньше. Основная проблема - худший случай. Лучшее случайное исправление - Introsort.
Большинство вариантов сортировки слияния имеют свой лучший, средний и наихудший случай, привязанный к n * log (n). Он стабилен и относительно прост в масштабировании. НО для этого требуется бинарное дерево (или его эмуляция) относительно размера общих элементов. Основная проблема - память. Лучшее случайное исправление - timsort.
Алгоритмы сортировки изменяются также по размеру ввода. Я могу сделать заявку новичков, что для ввода данных размера 10T нет совпадений для вариантов сортировки слияния.
ответ не затрагивает центральный вопрос, но он представляет ценную информацию о различных ролях, основанных на опыте реального мира. – MedicineMan
Вы также можете изучить другие типы сортировки, которые могут использоваться при определенных условиях. Например, рассмотрим сортировку Radix. http://en.wikipedia.org/wiki/Radix_sort
Я закончил с одним набором интервью в моем колледже прямо сейчас ...
Каждый алгоритм имеет свои преимущества, в противном случае он не будет существовать. Итак, лучше понять, что так хорошо с алгоритмом, который вы изучаете. Где это хорошо? как это может быть улучшено?
Я думаю, вам автоматически понадобится прочитать различные обозначения эффективности, когда вы это сделаете. Помните худший случай, и обратите внимание на средний случай, лучшие случаи встречаются редко.
Все самое лучшее для вашего интервью.
Я уверен, что ваш интервьюер завтрашнего дня не является таким обычным :) – DVK
Я не знаю, что не так с вопросами, чтобы улучшить ваши общие знания. Особенно, когда вы готовитесь к собеседованию, вы должны атаковать свои районы с наибольшей слабостью, не обращая внимания на лицо или как тупой вы можете смотреть. По моему опыту, те, кто больше всего боится выглядеть глупым, испытали наименьшее количество личного роста. – MedicineMan