Какие операции происходят быстро в NSSet и какие в NSArray?

Middle PRO

Суть

Разница — в структуре данных, а не в «скорости перебора».

• NSArray — упорядоченный список. Доступ по индексу objectAtIndex: — O(1); перебор — O(n); поиск containsObject:/indexOfObject: — O(n), потому что каждому элементу шлётся isEqual:. Вставка/удаление в середине NSMutableArray — O(n) (сдвиг элементов).
• NSSet — хеш-таблица без порядка и без дубликатов. containsObject:, addObject:, removeObject: — O(1) в среднем при корректных hash и isEqual:. Перебор — тоже O(n), но порядок не гарантирован. Операции над множествами (intersectSet:, minusSet:, isSubsetOfSet:) — O(n).

Перебор массива обычно чуть быстрее на практике (элементы лежат подряд, cache locality), но асимптотически это одинаково, и интервьюер ждёт не этого, а «поиск в массиве линейный, в множестве — константный».