Какая временная сложность (Big O) основных операций в стандартных коллекциях Swift?

Big O нотация описывает асимптотическую сложность алгоритмов в худшем случае. Для коллекций Swift:

• Array

  • Доступ по индексу (subscript): O(1)
  • Поиск значения (contains(_:)): O(n)
  • Вставка/удаление в конце (append(_:), removeLast()): O(1) (амортизированная)
  • Вставка/удаление в начале или середине (insert(_:at:), remove(at:)): O(n) (требуется сдвиг элементов)

    var array = [1, 2, 3]
    let element = array[1] // O(1)
    let exists = array.contains(2) // O(n)
    array.insert(0, at: 0) // O(n)

• Set

  • Поиск, вставка, удаление (contains(_:), insert(_:), remove(_:)): O(1) в среднем случае. Зависит от качества хэш-функции и коллизий.

• Dictionary

  • Доступ, вставка, удаление по ключу (subscript, updateValue(_:forKey:), removeValue(forKey:)): O(1) в среднем случае. Аналогично Set, зависит от хэширования.

• String (рассматривается как коллекция Character)

  • Многие операции, такие как доступ по индексу, имеют O(n), так как String в Swift состоит из расширенных кластеров графем (Unicode), и для нахождения n-го символа требуется итерация от начала строки.

Практический вывод: Выбор коллекции должен основываться на наиболее частых операциях. Для частого поиска по значению используйте Set. Для частого поиска по ключу — Dictionary. Для частого доступа по индексу и последовательной итерации — Array.