-[NSArray insertObject:atIndex:]
的复杂度是什么--N
还是常数?
另外,我如何找出各种Objective-C语句的复杂度?
-[NSArray insertObject:atIndex:]
的复杂度是什么--N
还是常数?
另外,我如何找出各种Objective-C语句的复杂度?
这里有一个讨论,CFArray.h源代码声明:
计算复杂度
对于数组中的值的访问时间保证在任何实现中最坏情况下为O(lg N),但通常为O(1)(常数时间)。类似地,线性搜索操作的最坏情况复杂度也是O(Nlg N),尽管在大多数情况下边界将更紧,等等。插入或删除操作通常与数组中的值数量成线性关系,但在某些实现中最坏情况下可能为O(Nlg N)。对于性能来说,数组内部没有优选位置;也就是说,不一定更快地访问具有低索引的值,或者插入或删除具有高索引的值,或者其他操作。
有趣的是,Foundation中数组的性能取决于数组的大小。
我认为没有任何网站详细说明Foundation中所有数据结构的性能,但是链接的文章提供了一种不错的观察分析方法,您可以将其应用于其他容器,如NSMutableDictionary。
据我所知,真正的"矩阵"并不存在,但这篇文章可以帮助解释为什么,同时回答主题中的问题:
http://ridiculousfish.com/blog/archives/2005/12/23/array/index.html
NSArray
或 CFArray
不是语言的一部分,它是一个核心基础类。您可以查看 CFArray源代码 来推断其复杂性,但这似乎需要一段时间 :) 如果您关心实际性能(而不是从理论角度提问),请进行测试和分析。官方文档没有说明,但我猜它类似于其他语言中的数组列表,时间复杂度应该是O(n)。