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

Так как PHP-массивы реализованы как хеш-таблицы, их операции имеют предсказуемую сложность.

Сложность основных операций

Перед разбором важно понимать, что речь идёт о средней сложности.

Вставка элемента

• Средняя сложность: O(1)

• Возможна перераспределение памяти при росте массива

$array['key'] = 'value';

Поиск по ключу

• Средняя сложность: O(1)

• Основан на хешировании ключа

$value = $array['key'];

Удаление элемента

• Средняя сложность: O(1)

• Элемент помечается как удалённый

unset($array['key']);

Итерация массива

• Всегда O(n)

• Нужно пройтись по всем элементам

foreach ($array as $value) {
    // обработка
}

Худшие случаи

• Коллизии хешей

• Перестройка таблицы при росте массива

На практике PHP хорошо оптимизирует эти сценарии.

Краткий вывод

PHP-массивы быстры для доступа по ключу, но любая полная обработка массива линейна. Это важно учитывать при работе с большими объемами данных.