0
中位數quicksort的中位數的最壞情況時間複雜度是什麼（數據的中位數取決於需要O（n）時間才能找到的中位數）？中位數quicksort中位數的最壞情況時間複雜度是多少？
A
回答
2
近似中值選擇算法也可以被用作在快速排序樞軸策略，產生一個最佳的算法，與最壞情況下的複雜度爲O（n log n）的。
這是因爲中位數算法的中位數可以防止在已排序的數組上發生天真快速排序的錯誤分區。
相關問題
- 1. 最佳情況和最壞情況下的時間複雜度
- 2. 最壞情況下的時間複雜
- 3. 最壞的情況會是什麼時間複雜度？
- 4. 算法的最壞情況複雜度
- 5. 給定函數的最壞情況時間複雜度是什麼？
- 6. 時間複雜度 - 計算算法的最壞情況
- 7. 散列的最壞情況時間複雜度（插入）
- 8. 最壞情況下的時間複雜度
- 9. 將節點插入二叉搜索樹中的最壞情況時間複雜度是多少？
- 10. 從雙棧隊列中出隊的最壞情況時間複雜度是多少？
- 11. 時間複雜度（Java，Quicksort）
- 12. Medians空間複雜度中位數
- 13. 方案中'assoc'函數的時間複雜度是多少？
- 14. clojure中count函數的時間複雜度是多少？
- 15. C++中std :: next_permutation（）函數的時間複雜度是多少？
- 16. Collection.toArray（）的時間複雜度是多少？
- 17. 確定最壞情況算法的時間複雜性
- 18. 證明QuickSort的最壞情況下運行時間
- 19. 最差情況時間深度優先搜索的複雜度
- 20. 下面的遞歸函數的時間複雜度是多少
- 21. 計算遞歸算法的最壞情況運行時間複雜度
- 22. 鏈式哈希表查找的預期最壞情況時間複雜度？
- 23. 計算算法的最壞情況下運行時間複雜度
- 24. 這個函數的時間複雜度是多少？
- 25. 添加n個數字的時間複雜度是多少
- 26. 劃分兩個數字的時間複雜度是多少？
- 27. 密碼散列函數的時間複雜度是多少？
- 28. 最近遞歸找到max的時間複雜度是多少
- 29. 我的代碼中的時間複雜度是多少
- 30. Java中TreeSet的lower（）/ higher（）的時間複雜度是多少？
如果我記得我的算法正確，我認爲它是'O（n^2）'。 – 2014-11-22 13:43:24
爲什麼？中位數的中位數確保了每種情況下的良好分區。 – 2014-11-22 13:47:01