sortedArrayUsingComparator的时间复杂度（大O表示法）是什么？iOS/OSX

Question

我需要知道NSArray类的sortedArrayUsingComparator函数的时间复杂度。最好能提供参考资料，因为我可能会在我的学士论文中提到它。我正在按照与当前位置的距离对位置数组进行排序。

我找到的唯一答案是有人说它至少是T(n)=O(n)，但很可能是T(n)=O(n log n)。

我如何确定它的确切时间复杂度？

- VeryPoliteNerd

Answer 1

通过实际测试，NSArray的排序时间符合 O(n*log(n))。

查看博客文章

请注意，在评论中有一种排序方法（PS9110）是O(n)的，但它是专有且受专利保护的。这个方法非常有趣。

- zaph

Answer 2

要对数组进行排序，至少需要查看每个元素，这肯定是O(n)的。有一些数学论文表明，没有比例如Mergesort的更好的排序算法，其时间复杂度为O(n*log(n))。由于比较器实现了Mergesort，因此我认为最好、平均和最差情况下的复杂度应该为O(n*log(n))。

您可以在此处找到有关Mergesort的一些信息： Mergesort 还有一些关于最佳排序算法时间复杂度的文章： Sorting algorithms 我找不到给定方法的确切实现，但这里有一篇很棒的文章，介绍了如何深入挖掘Objective-C中的数组实现，以及查看方法的实现： Exposing NSMutableArray

- dehlen