Что такое нотация big-O для итерации через NSSet и NSDictionary

Question

Мне было интересно, что такое нотация big-O для итерации через NSSet. Ответ для NSArray, очевидно, O(n) - но каков ответ для NSSet? Кроме того - я предполагаю, что тот же ответ будет применяться для NSDictionary?

Answer 1

Вы можете получить некоторое представление о вычислительной сложности структур данных Apple, посмотрев на комментарии в заголовках их мостовых эквивалентов Core Foundation (поскольку они по сути используют тот же самый код под капотом).

Интересно, что сложность времени CFArray фактически не гарантируется, что будет O(n):

Вычислительная сложность

Время доступа для значения в массиве гарантированно будет худшим O(lg N) для любой реализации, текущей и будущей, но часто будет O(1) (постоянное время). Операции линейного поиска аналогично имеют сложность O(N*lg N) в худшем случае, хотя обычно границы будут более жесткими и так далее. Операции вставки или удаления, как правило, будут линейными по количеству значений в массиве, но в некоторых реализациях могут быть явно равны O(N*lg N) в худшем случае. В массиве нет предпочтительных позиций для производительности; то есть не обязательно быстрее получать доступ к значениям с низкими индексами или вставлять или удалять значения с высокими индексами, или что-то еще.

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

Аналогично для CFDictionary Указанные границы имеют довольно широкий диапазон:

Вычислительная сложность

Время доступа к значению в словаре гарантированно будет наихудшим O(N) для любой реализации, текущей и будущей, но часто будет O(1) (постоянное время). Операции вставки или удаления, как правило, также будут иметь постоянное время, но в некоторых реализациях имеют значение O(N*N) в худшем случае. Доступ к значениям через ключ быстрее, чем прямой доступ к значениям (если есть такие операции). Словари будут стремиться использовать значительно больше памяти, чем массив с таким же количеством значений.

Мне не удалось найти аналогичный комментарий в заголовках Core Foundation для CFSet, но проверка исходного кода показывает, что он основан на CFBasicHash, которая является хеш-таблицей, поэтому сложность по времени будет такой же, как типичная для хеш-таблицы - O (1) вставка, удаление и тестирование обычно и O (n) в худшем случае.

Если вам действительно интересно узнать, как именно работают эти структуры данных, Core Foundation имеет открытый исходный код, поэтому вы можете прочитать исходный код на веб-сайте Apple.