Какая временная сложность поиска по ключу в словаре (Dictionary) в Swift?

O(1) в среднем случае, но может деградировать до O(n) в худшем.

Объяснение: Dictionary реализован как хеш-таблица.

1. Средний случай (O(1)): Хеш-функция вычисляет индекс корзины (bucket) для ключа, обеспечивая почти мгновенный доступ. Коллизии (разные ключи с одинаковым хешем) разрешаются методами вроде цепочек или открытой адресации, но при хорошем распределении хешей и достаточном размере таблицы доступ остается константным.
2. Худший случай (O(n)): Возникает при множественных коллизиях, когда все ключи попадают в одну корзину, и поиск превращается в линейный обход.

Пример:

var capitals = ["France": "Paris", "Japan": "Tokyo", "Brazil": "Brasília"]
let city = capitals["Japan"] // O(1) в среднем

Практический вывод: Для типов с качественной хеш-функцией (как стандартные) сложность эффективна. Избегайте использования в качестве ключей типов с плохим хешированием.