6
我需要知道NSArray類的 sortedArrayUsingComparator函數的時間複雜度。一個消息來源會很棒，因爲我很可能在我的學士論文中提到它。 我正按距離排序位置數組到當前位置。sortedArrayUsingComparator的時間複雜度（大O）是什麼？ iOS/OSX
我能找到的唯一答案是有人說這是至少T（N）= O（N），但有可能T（N）=爲O（n log n）的
我怎麼會知道肯定？
A
回答
3
0
基於比較成本的排序算法至少爲O（n log n）。看到這個link
由於其名稱sortedArrayUsingComparator顯示，該方法是基於比較，所以它會花費至少O（n log n）。
1
那麼要排序數組，你必須至少看看每個元素是肯定的O(n)。有幾篇數學論文向您展示，例如，之類的O(n*log(n))不能有更好的排序算法。由於比較器實現了Mergesort我認爲複雜性應該是O(n*log(n))最好，平均和最壞的情況。
你可以找到一些有關Mergesort這裏： Mergesort
而且有些文章關於最好的排序算法的時間複雜度：
我找不到給定方法的具體實現，但在這裏是一篇很好的文章，您可以更深入地瞭解Objective-C中的數組實現以及查看方法實現： Exposing NSMutableArray
相關問題
- 1. 計數排序O（n + k）時間複雜度是什麼k？
- 2. 時間複雜度：O（logN）或O（N）？
- 3. 以下是什麼時間複雜度？
- 4. 爲什麼這個算法的空間複雜度是O（1）
- 5. 爲什麼代碼O（log n）的時間複雜度？
- 6. 簡單的時間複雜度O（nlogn）
- 7. 非大O複雜度
- 8. 什麼是陣列的時間複雜度和空間複雜度[:: - 1]
- 9. 這是什麼意思：「檢測到的時間複雜度：O（（N + M）* K）」？
- 10. 合併排序時間複雜度與我的算法。大O
- 11. 如何找到while循環的時間複雜度（大O）？
- 12. 時間複雜度在Python - 大O符號
- 13. 時間複雜度O（N日誌（log n）的）+ N O（L）
- 14. 確定函數的大O複雜度
- 15. 算法的大O複雜度
- 16. SQL - 外鍵O（1）的時間複雜度是多少？
- 17. 是這個算法的漸近時間複雜度O（log n）？
- 18. 替代O（N^2）的時間與O（1）空間複雜度的複雜度在陣列
- 19. 爲什麼後綴樹中發生的複雜度是O（mn）？
- 20. 爲什麼我的底部複雜度不是O（n^3）
- 21. 這種方法的大O複雜性是什麼？
- 22. 複雜性大O
- 23. 大O符號中下列代碼的時間複雜度是多少？
- 24. 時間複雜度 - O（n^2）到O（n log n）搜索
- 25. 什麼是java.util.HashMap類的keySet（）方法的時間複雜度？
- 26. 什麼是下面的算法的時間複雜度
- 27. 什麼是R +樹操作的時間和內存複雜度？
- 28. 時間複雜度和運行時間之間的關係是什麼？
- 29. 爲什麼這個循環需要O（2^n）時間複雜度？
- 30. 爲什麼while循環對總時間複雜度貢獻O（n）？