Сложность 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 зависит от размера массива .

Я не думаю, что есть какой-либо сайт, который объясняет производительность всех структур данных в Основа, но связанная статья дает хороший обзорный анализ, который можно повторить для других контейнеров, таких как NSMutableDictionary.

Answer 3

действительно нет матрицы (afaik), но этот пост должен помочь объяснить почему , а также ответить на вопрос в теме:

http://ridiculousfish.com/blog/archives/2005/12/23/array/index.html

Answer 4

Просто гадость: NSArray или CFArray не является частью языка, это базовый класс Foundation. Вы можете взглянуть на исходный код CFArray , чтобы понять его сложность, но, похоже, это займет некоторое время :) Если вы беспокоитесь о производительности в реальном мире (в отличие от теоретических вопросов зрения), сделать тест и профиль.

Answer 5

Официальные документы не утверждают это, но я думаю, что это похоже на списки массивов на других языках, которые были бы O (n).