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

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

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

Спасибо

Ответы

Ответ 1

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

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

Цитата из http://php.net/manual/en/function.array-unique.php

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