sortedArrayUsingComparator的時間複雜度（大O）是什麼？ iOS/OSX

我需要知道NSArray類的 sortedArrayUsingComparator函數的時間複雜度。一個消息來源會很棒，因爲我很可能在我的學士論文中提到它。我正按距離排序位置數組到當前位置。sortedArrayUsingComparator的時間複雜度（大O）是什麼？ iOS/OSX

我能找到的唯一答案是有人說這是至少T（N）= O（N），但有可能T（N）=爲O（n log n）的

我怎麼會知道肯定？

通過NSArray排序時間的實際測試符合O(n*log(n))。

注意，在評論有一種方法（PS9110），這是O（n），但專有和專利。該方法非常有趣。

2015-04-17 12:17:51 zaph

基於比較成本的排序算法至少爲O（n log n）。看到這個link

由於其名稱sortedArrayUsingComparator顯示，該方法是基於比較，所以它會花費至少O（n log n）。

2015-04-17 11:46:18 KudoCC

那麼要排序數組，你必須至少看看每個元素是肯定的O(n)。有幾篇數學論文向您展示，例如，之類的O(n*log(n))不能有更好的排序算法。由於比較器實現了Mergesort我認爲複雜性應該是O(n*log(n))最好，平均和最壞的情況。

你可以找到一些有關Mergesort這裏： Mergesort

而且有些文章關於最好的排序算法的時間複雜度：

我找不到給定方法的具體實現，但在這裏是一篇很好的文章，您可以更深入地瞭解Objective-C中的數組實現以及查看方法實現： Exposing NSMutableArray

2015-04-17 11:47:44 dehlen

回答