Количество действий array_unique PHP

Question

Кто-нибудь знает Big O из array_unique()?

Я не прошел через источник, но я хотел бы представить, что он проходит через каждое значение и проверяет, есть ли оно в массиве, который будет O(n^2) это правильно?

Спасибо

Answer 1

Это O(nlogn) так как он использует сортировку вместо вашего O(n^2) сканирования.

Обратите внимание, что ключи сохранены. array_unique() сначала сортирует значения, которые обрабатываются как строки, затем сохраняет первый ключ, найденный для каждого значения, и игнорирует все последующие ключи. Это не означает, что ключ первого связанного значения из несортированного массива будет сохранен.

Цитируется с http://php.net/manual/en/function.array-unique.php

РЕДАКТИРОВАТЬ: не забудьте Google, проверить руководство, проверить существующие вопросы, а затем задать его.