Один шаг при любом размере
O(1) означает постоянное время: операция занимает одно и то же число шагов независимо от того, содержит вход 5 элементов или миллион. Объём работы вообще не растёт.
Это наилучшая возможная сложность. Типичные операции O(1) в PHP: чтение элемента массива по индексу или по ключу, count(), добавление одного элемента с помощью $arr[] = ... и простая арифметика.
Обратите внимание, чего O(1) не означает: это не значит «быстро», это значит «не становится медленнее при росте входных данных». Один постоянный шаг всё ещё может быть медленным шагом — но он остаётся одним шагом.
Поиск по индексу и по ключу
Массив в PHP находит элемент прямо по его ключу, поэтому $words[2] — это один переход: движок не проходит по элементам, стоящим перед ним. То же чтение стоит столько же и в массиве из миллиона элементов.
Строковые ключи работают так же: $ages["Ben"] находит значение напрямую, в среднем за постоянное время. С отсутствующим ключом нужна осторожность: простое $ages["Dan"] вызывает предупреждение и даёт null, поэтому безопасное чтение — это $ages["Dan"] ?? null: оператор ?? тихо возвращает значение по умолчанию, когда ключа нет.
Чтение элемента по индексу
Программа читает один элемент из массива на 5 элементов и один из массива на миллион элементов. Оба чтения — это один шаг; длина массива никакой роли не играет.
Вывод: PHP-скрипт
<?php
$words = ["one", "two", "three", "four", "five"];
$big = [];
for ($i = 0; $i < 1000000; $i++) {
$big[$i] = $i * 2;
}
// По одному шагу на каждое чтение, независимо от длины массива.
echo $words[2], "\n";
echo $big[999999], "\n";
Чтение значения по ключу
$ages["Ben"] ?? null находит 25 напрямую. Отсутствующий ключ "Dan" сводится к значению по умолчанию из ?? и даёт NULL — по-прежнему за постоянное время. Без ?? чтение отсутствующего ключа сначала вызвало бы предупреждение.
Вывод: PHP-скрипт
<?php
$ages = ["Ana" => 30, "Ben" => 25, "Cleo" => 41];
$age = $ages["Ben"] ?? null;
echo "Ben: ", var_export($age, true), "\n";
$age = $ages["Dan"] ?? null;
echo "Dan: ", var_export($age, true), "\n";
Добавление в конец и простая арифметика
$colors[] = ... добавляет один элемент в конец массива. Почти всегда это один шаг. (Изредка внутреннему хранилищу приходится расти и оно копируется, но в среднем стоимость одного добавления остаётся постоянной.)
Все небольшие операции — присваивания, сложения, сравнения, обмен двух значений — тоже O(1). Это те самые «шаги», в которых считаются все остальные классы сложности.
Добавление одного элемента
$colors[] = "yellow" помещает "yellow" в конец. Стоимость не зависит от того, сколько цветов уже есть в массиве.
Вывод: PHP-скрипт
<?php
$colors = ["red", "green", "blue"];
echo "до: ", implode(", ", $colors), " (количество: ", count($colors), ")\n";
$colors[] = "yellow";
echo "после: ", implode(", ", $colors), " (количество: ", count($colors), ")\n";
Обмен двух значений
[$a, $b] = [$b, $a] меняет два значения местами за один шаг постоянного времени — вспомогательная переменная не нужна.
Вывод: PHP-скрипт
<?php
$a = 1;
$b = 2;
echo "до: $a $b\n";
[$a, $b] = [$b, $a];
echo "после: $a $b\n";