Какая временная сложность у операций: вставка, удаление, поиск по ключу, итерация массива?

Question

Вставка и поиск по ключу в PHP-массиве выполняются за константное время в среднем. Удаление также работает быстро. Итерация всегда линейная. В худших случаях сложность может ухудшаться, но на практике это редкость.

YeaHub · Accepted Answer

Так как PHP-массивы реализованы как хеш-таблицы, их операции имеют предсказуемую сложность.Сложность основных операцийПеред разбором важно понимать, что речь идёт о средней сложности.Вставка элементаСредняя сложность: O(1)Возможна перераспределение памяти при росте массива$array['key'] = 'value';
Поиск по ключуСредняя сложность: O(1)Основан на хешировании ключа$value = $array['key'];
Удаление элементаСредняя сложность: O(1)Элемент помечается как удалённыйunset($array['key']);
Итерация массиваВсегда O(n)Нужно пройтись по всем элементамforeach ($array as $value) {
    // обработка
}
Худшие случаиКоллизии хешейПерестройка таблицы при росте массиваНа практике PHP хорошо оптимизирует эти сценарии.Краткий выводPHP-массивы быстры для доступа по ключу, но любая полная обработка массива линейна. Это важно учитывать при работе с большими объемами данных.