插入对象:在索引处的复杂度

Question

-[NSArray insertObject:atIndex:]的复杂度是什么--N还是常数？

另外，我如何找出各种Objective-C语句的复杂度？

- user4951

Answer 1

这里有一个讨论，CFArray.h源代码声明：

计算复杂度
对于数组中的值的访问时间保证在任何实现中最坏情况下为O(lg N)，但通常为O(1)（常数时间）。类似地，线性搜索操作的最坏情况复杂度也是O(Nlg N)，尽管在大多数情况下边界将更紧，等等。插入或删除操作通常与数组中的值数量成线性关系，但在某些实现中最坏情况下可能为O(Nlg N)。对于性能来说，数组内部没有优选位置；也就是说，不一定更快地访问具有低索引的值，或者插入或删除具有高索引的值，或者其他操作。

- Manny

Answer 2

有趣的是，Foundation中数组的性能取决于数组的大小。

我认为没有任何网站详细说明Foundation中所有数据结构的性能，但是链接的文章提供了一种不错的观察分析方法，您可以将其应用于其他容器，如NSMutableDictionary。

- Caleb

Answer 3

据我所知，真正的"矩阵"并不存在，但这篇文章可以帮助解释为什么，同时回答主题中的问题：

http://ridiculousfish.com/blog/archives/2005/12/23/array/index.html

- justin

Answer 4

只是挑剔一下： NSArray 或 CFArray 不是语言的一部分，它是一个核心基础类。您可以查看 CFArray源代码 来推断其复杂性，但这似乎需要一段时间 :) 如果您关心实际性能（而不是从理论角度提问），请进行测试和分析。

- zoul

Answer 5

官方文档没有说明，但我猜它类似于其他语言中的数组列表，时间复杂度应该是O(n)。

- Rudy Velthuis

---

有趣的是，（正如Manny所指出的那样）CFArray标头提供了一些性能细节，并且其表现更像哈希表：在最坏情况下访问时间复杂度为O(log N)。 - jscs

@Josh：是的，我注意到了。看着CFArray.c，它似乎是一个相当复杂的类型（尽管我不知道为什么它必须如此复杂）。 - Rudy Velthuis