1. 首頁
  2. 問答
  3. 排序算法的效率

排序算法的效率

2009-09-13 107 views
4

我正在研究明天的一個非常重要的採訪，有一件事情我有很多麻煩：排序算法和BigO效率。排序算法的效率

什麼數字很重要？最佳，最差或平均效率？

來源

2009-09-13 MedicineMan

+1

我當然希望你明天的面試官是不是因此定期:) – DVK 2009-09-13 17:18:33

+14

我不知道什麼是錯的問問題，以提高你的一般知識。特別是在準備面試時，你應該攻擊你最擅長的領域，而不考慮面子或者看起來多麼笨。根據我的經驗，那些最害怕看起來像個傻瓜的人所經歷的個人成長最少。 – MedicineMan 2009-09-13 18:02:25

回答

4

最差，其次是平均水平。也要意識到所謂的「隱藏常量」的真實世界影響 - 例如，經典的快速排序算法在最壞的情況下爲O（n^2），平均爲O（n log n），而mergesort在最壞的情況下是O（n log n），但在實踐中快速排序將優於合併排序。

來源

2009-09-13 17:02:51

+0

自然歸併可以離開快速排序和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/等等。 – 2009-09-13 17:13:30

+4

雖然這是一個很好的答案，但我必須管理員我會猶豫不決僱傭一些不明白開發者這種基本和顯而易見的東西。 – DVK 2009-09-13 17:17:56

+0

DVK，你聽起來像是一個象牙塔般的人，那種以最大努力小心翼翼地守衛他知識面不大的人。你是不是在這裏分享你的知識，你的努力來支持社區？你擔心有人會在這方面獲得勝任能力，然後拿到你的工作？ – MedicineMan 2009-09-13 18:05:43

2

當然，所有這些都很重要。你必須明白一種排序算法的好處，在最糟糕的情況下，平均情況下可能會變成可怕的赤字，或者最糟糕的情況並不是那麼糟糕，但最好的情況並不是那麼好，它只適用於未分類的數據等。

來源

2009-09-13 17:03:56

1

我建議你不要只記住這些事實。瞭解他們爲什麼如此。如果我正在採訪你，我會確保提出問題，告訴你我理解如何分析算法，而不僅僅是吐出你在網頁或書中看到的東西。另外，面試之前的一天並不是進行這項學習的時間。

祝你好運！請在評論中報告它是如何去的！

來源

2009-09-13 17:14:03

+0

謝謝，記憶永遠不是最好的路線，但是當面臨最後期限時，我需要優先考慮大腦中發生的事情。 – MedicineMan 2009-09-13 18:06:57

2

總之。

排序算法效率會因輸入數據和任務而異。

  • 排序最高速度，可以存檔就是n *的log（n）
  • 如果數據包含排序的子數據，最高速度可以得到更好的那麼n *的log（n）
  • 如果數據包括重複，排序可以在接近線性的時間來完成
  • 大多數排序算法都有其用途

最快速排序的變種有它的平均情況也的n * log（n）的，但你通常快於其他沒有嚴格優化的算法。它不穩定時速度更快，但穩定的變體速度只有一小部分慢。主要問題是最壞的情況。最好的休閒解決方案是Introsort。

大部分合並排序變體的最佳，平均和最壞情況都固定爲n * log（n）。它穩定並且相對容易擴展。但它需要一個相對於總項目大小的二叉樹（或其仿真）。主要問題是記憶。最好的臨時解決方法是timsort。

排序算法也因輸入大小而異。我可以做一個新手聲稱，超過10T大小的數據輸入，沒有合併排序變種的匹配。

來源

2009-09-13 18:27:45 Margus

+0

答案沒有解決發佈的中心問題，但它確實提供了基於現實世界經驗的各種排序表現的寶貴洞察力。 – MedicineMan 2009-09-13 18:33:47

1

我剛剛在我的大學剛剛結束了一組面試......

每個算法有它的好處，否則不會存在。 因此，它更好地理解您正在研究的算法的優點。它在哪裏做得好？如何改進？

我想你需要自動執行此操作時讀取各種效率符號。注意最壞的情況，並注意平均情況，最好的情況是罕見的。

一切順利您的採訪。

來源

2009-09-14 16:33:57 Lazer

相關問題

 相關問題