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）？