insertObject 的复杂性:atIndex: [英] Complexity of insertObject:atIndex:

问题描述

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

What is the complexity of -[NSArray insertObject:atIndex:] -- N? or constant?

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

Also, how can I find out the complexity of various Objective-C statements?

推荐答案

这里有一个讨论 和 CFArray.h 源代码状态:

There is a discussion here and CFArray.h source code states:

计算复杂性
数组中某个值的访问时间为对于任何实现，当前和未来，但通常是 O(1)(恒定时间).线性搜索操作同样具有 O(Nlg N) 的最坏情况复杂度，虽然通常界限会更紧，等等.插入或删除操作通常与值的数量呈线性关系在数组中，但在某些情况下，在最坏的情况下显然可能是 O(Nlg N)实现.阵列中没有有利位置表现;也就是说，访问值不一定更快具有低索引，或插入或删除具有高索引的值，或随便.

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.

这篇关于insertObject 的复杂性:atIndex:的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！