Если вы подозреваете, что в массиве очень мало разных значений, сканирование массива для извлечения этих значений, их сортировки и подсчета займет значительно меньше времени, чем полная сортировка слиянием массива:
- Если вы используете хеш-таблицу, выбор значений займет O (N) время, создав массив выборки размером log (N) .
- сортировкаэтот образец массива должен занять O (log (N) .log (log (N)) , незначительно по сравнению с фазой сканирования.
- перечисление образца массива для генерации копий в исходный массив)также имеет линейную сложность по времени O (N) .
Следовательно, сложность по времени может быть уменьшена до O (N) .
Однако обратите внимание, что:
- с использованием хеш-таблицы может оказаться невозможным для создания образца массива. Если вместо этого вы создадите отсортированный список, сложность вернется к O (N.log (N)) из-за линейного поиска в массиве образцов для каждого элемента.
- генерация копий элементов может быть недостаточной, если элементы исходного массива имеют идентичные ключи, но разное содержимое.В этом случае вы должны отсканировать исходный массив и найти ключ элемента в образце массива, чтобы определить, где хранить элемент в результирующем массиве, снова O (N.log (N)) сложность времени, еслиобразец массива представляет собой список, и O (N.log (log (N))) , если это массив, и вы используете бинарный поиск.
Как заключение,сложность может быть эффективно уменьшена в особых случаях, но в общем случае она сложна.