insertObject的复杂性:atIndex:

Question

什么是复杂性-[NSArray insertObject:atIndex:]- N？还是不变？

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

Answer 1

这里有一个讨论和CFArray.h源代码说明:

计算复杂性
对于任何实现,当前和未来,数组中值的访问时间保证最差为O(lg N),但通常为O(1)(恒定时间).类似地,线性搜索操作具有O(N lg N)的最差情况复杂度,但是通常边界将更紧密,等等.插入或删除操作通常在阵列中的值的数量上是线性的,但在一些实现中在最坏的情况下可以清楚地为O(N lg N).阵列中没有优势位置用于表现; 也就是说,访问具有低索引的值,或者插入或删除具有高索引的值,或其他任何东西,都不一定更快.

Answer 2

有趣的是,Foundation中数组的性能取决于数组的大小.

我认为没有任何网站可以说明Foundation中所有数据结构的性能,但链接的文章提供了一个很好的观察分析,你可以重复其他容器,如NSMutableDictionary.