Geek Answers Handbook

Difficulty insertObject: atIndex:

What is the difficulty -[NSArray insertObject:atIndex:]- N? or a constant?

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

+5
source share
5 answers

The discussion and source code for CFArray.h are discussed here:

Computational complexity
The access time for a value in an array is guaranteed to be in the worst case O (log N) for any implementation, current and future, but often there will be O (1) (constant time). Linear search operations likewise have worse O (Nlg N) complexity, although usually the boundaries will be stricter and so on. Insertion or deletion operations will usually be linear in the number of values ​​in the array, but may be O (Nlg N) explicitly in the worst case in some Implementations. There are no favorable positions in the array for presentation; that is, it is not necessary to access values ​​with low indices faster or to insert or delete values ​​with high indices or whatever.

+6
source

, Foundation .

, , Foundation, , , NSMutableDictionary.

+5

Just a nit choice: NSArrayor CFArraynot part of the language, its Core Foundation class. You can take a look at the source code of CFArray to justify its complexity, but it looks like it will take some time :) If you are concerned about the real work (unlike the theoretical point of view), do the test and profile.

+1
source

This is not stated in the official docs, but I think it looks like lists of arrays in other languages ​​that would be O (n).

0
source

More articles:


All Articles