Существует ли аналогичный доступный через Интернет документ со списком гарантий сложности для NSArray, NSDictionary и т. Д .?
Нет.Если вы понимаете, что делают разные контейнеры, у вас будет довольно хорошее представление о том, как они ведут себя (например, словарь == карта -> поиск почти в постоянном времени).Но не думайте, что вы точно знаете, как ведут себя эти структуры, потому что они могут изменять свое поведение в зависимости от обстоятельств .Другими словами, такой класс, как NSArray, не может быть (конечно, не) реализован как фактический массив в смысле массива в стиле C, даже если он имеет такое же поведение «упорядоченной последовательности элементов».* Конечно, вы можете проанализировать сложность вашего собственного кода: ваш собственный бинарный поиск через NSArray всегда будет выполнять O (log n) операций, как бы вы их ни вырезали.Только не думайте, что для вставки элемента в NSMutableArray потребуется переместить все последующие элементы, потому что ваш «массив» действительно может быть связанным списком или чем-то еще.