objective-c - insertObject 的复杂度 :atIndex:

Question

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

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

Answer 1

有一个discussion here和 CFArray.h 源代码状态:

Computational Complexity
The access time for a value in the array is guaranteed to be at worst O(lg N) for any implementation, current and future, but will often be O(1) (constant time). Linear search operations similarly have a worst case complexity of O(Nlg N), though typically the bounds will be tighter, and so on. Insertion or deletion operations will typically be linear in the number of values in the array, but may be O(Nlg N) clearly in the worst case in some implementations. There are no favored positions within the array for performance; that is, it is not necessarily faster to access values with low indices, or to insert or delete values with high indices, or whatever.