1
親愛的朋友們，
當我讀到一些算法的信息，偶爾，我遇到算法性能信息，如：O（1），O（n），O（n^2）等等。
我能否解釋如何翻譯和理解此性能數據？什麼樣的O（n）變體可用，它們在實踐中意味着什麼？
謝謝。
A
回答
7
您需要對big-O符號進行解釋。
它是一種算法複雜度的度量。由於N趨於無窮大，所需時間的方向就是這樣。
你需要注意的一件事是O（N）乘以常數仍然是O（N）。沒有像O（2N）那樣的東西。 O（1）意味着需要一個固定的時間，即所花費的時間量與您正在處理的數據量無關。 O（N）表示它與您正在處理的數據量成正比，因此如果處理一百萬條記錄需要一分鐘時間，則需要2分鐘來處理200萬條記錄。
O（N^2）意味着它是成比例的N. 1000記錄的方需要一分鐘，2000需要4分鐘，4000需要16分鐘等
可以還O（日誌N ）和O（N log N）。您可以使用任何基礎進行日誌記錄，但通常使用日誌基數2進行度量。因此，一百萬條記錄將測量爲20，因爲2^20接近一百萬，而200萬條記錄將是21.對於N日誌N，一千條記錄將相當於10,000，因爲1000的日誌大約爲10. 2000個記錄將是22,000，因爲2000的日誌大約爲11.
1
相關問題
- 1. heapify O（n）算法
- 2. O（n）排序算法可能嗎？
- 3. 證明最大（O（f（n）），O（g（n）））= O（max（f（n），g（n））
- 4. 算法與O（N /日誌（n））的複雜性
- 5. 優化算法（N^3）爲O（n^2）
- 6. 證明5^n = o（n！）
- 7. 證明lg（n！）= O（n！）
- 8. 證明O（max {f（n），g（n）} = O（f（n）+ g（n））
- 9. 使用Prim算法從O（n^3）到O（n^2）優化MST
- 10. 堆性能低下。 O（n）而不是\t O（日誌n）
- 11. 想出一種算法，O（n）的
- 12. O（n）中的2鍵搜索算法
- 13. 圖的O（m + n）時間算法
- 14. floor（√2n）的O（log log n）算法？
- 15. O（n）的運行時間算法
- 16. 我怎樣才能使O（N）而不是O（N^2）的性能？
- 17. O（N + m）和O（NM）之間的複雜性計算差異
- 18. 說明上HyperLogLog算法
- 19. 提高爲O（n^2）算法
- 20. O（fib n）複雜度算法？
- 21. 爲什麼這個算法O（N）？
- 22. 龜和兔算法總是O（N）？
- 23. 這個算法如何O（n）？
- 24. Sum算法：O（n^2）平均值
- 25. 性能分析說明
- 26. 證明2 ^（n a）= O（2^n）？
- 27. 在漸近分析中，證明：O表示大O. O（f（n）+ g（n））= O（max {f（n），g（n）}）
- 28. 如何計算O（Log（N））？
- 29. 通用實用的排序算法比O（n log n）快嗎？
- 30. 實施例（2^N）算法
維基百科是你的朋友在這裏。它有一個很好的文章。 http://en.wikipedia.org/wiki/Big_O_notation – 2011-01-23 20:14:37
可能重複（其中包括）[大O的純英語解釋]（http://stackoverflow.com/questions/487258/plain-english-explanation-of-大o） – delnan 2011-01-23 20:15:02
謝謝，我已經在閱讀維基百科。最好的祝福。 – 2011-01-23 20:24:16