Какова временная сложность добавления элемента в массив?
РНР массивы сложные звери; они позволяют осуществлять быстрый поиск, как обычная хеш-таблица, но их пары ключ-значение также упорядочены. Как меняются временные затраты на вставку элемента в эту структуру по мере роста количества существующих элементов?
Зависит ли сложность времени от того, как именно я вставляю элемент в массив? Например, выполните каждую из этих операций:
array_unshift($array, $value);
array_push($array, $value);
array['some_new_key'] = $value;
имеют одинаковую сложность времени или разные временные сложности?
Решение
Постоянное время O (1)
array_push является постоянным временем (функция очереди для структуры, подобной хэш-таблице), однако интересно отметить, что это связано с производительностью:
array_push();
$array[] = $val;
Последний метод быстрее, чем array_push из-за отсутствия затрат на оплату служебных вызовов.
Линейное время O (n)
определенно array_push и связанные функции очереди намного быстрее, чем array_unshift, Да, все они выполняют одну и ту же функцию, но разными способами для достижения этой цели. Как вы уже отметили, массивы PHP чрезвычайно мощны и обеспечивают надежную функциональность. Это обходится дорого, поскольку в массивах PHP есть упорядоченные ключи, и вам необходимо заплатить дополнительную плату за повторную индексацию всех этих ключей, поэтому O(n), array_unshift Затем потребуется линейное время массива + постоянное время, чтобы добавить значения в начало массива, так что-то похожее на O(n + cn'), где c постоянное время добавления элемента в массив, а n ‘- количество добавляемых элементов.
Другие решения
array_push($array, $value);
а также
array['some_new_key'] = $value;
оба O (1)
array_unshift($array, $value);
равно O (n), потому что (изменяя «голову») он должен перетасовать весь массив для обработки порядка