Сортировка подсчетом — это алгоритм сортировки со средней временной сложностью O(n+K), а сортировка подсчетом предполагает, что каждый входной элемент является целым числом в диапазоне от 0 до K.
Почему мы не можем линейно найти максимальное значение в несортированном массиве, приравнять его к K и, следовательно, применить к нему сортировку подсчетом?
В случае, когда ваши входные данные представляют собой массивы с maximum - minimum = O(n log n) (т.е. диапазон значений разумно ограничен), это действительно имеет смысл. Если это не так, стандартный алгоритм сортировки на основе сравнения или даже алгоритм целочисленной сортировки, такой как сортировка по основанию, асимптотически лучше.
Чтобы дать вам пример, следующий алгоритм генерирует семейство входных данных, для которых сортировка подсчетом имеет сложность времени выполнения Θ(n^2):
def generate_input(n):
array = []
for i := 1 to n:
array.append(i*i);
shuffle(array)
return array
f(n) будет временем выполнения сортировки подсчетом для данного семейства входных данных. У нас есть f(n) = Θ(n + k) = Θ(n^2), следовательно, мое утверждение верно.
- person Niklas B.; 27.12.2014
Ω(n + k) и O(n + k), если k — это O(n). Таким образом, использование чисел, намного превышающих длину массива, как упоминал Никлас, нарушает предварительное условие, которое делает Θ(n + k). Итак, если в массиве есть k = Θ(nˆ2), то временная сложность становится Θ(n^2).
- person JP Ventura; 27.12.2014
Заголовок вашего вопроса: Почему сортировка подсчетом не используется для больших входных данных?
Что мы делаем в счетной сортировке? Мы берем другой массив (предположим, b[]) и инициализируем все элементы нулем. Затем мы увеличиваем индекс, если этот индекс является элементом данного массива. Затем мы запускаем цикл от нижнего предела до верхнего предела данного массива и проверяем, равен ли элемент индекса моего взятого массива (b[]) 0 или нет. Если он не равен нулю, это означает, что этот индекс является элементом данного массива.
Теперь, если разница между этими двумя (верхний предел и нижний предел) очень велика (например, 10 ^ 9 или более), то одного цикла достаточно, чтобы убить наш компьютер. :)
std::map для индексации элемента этого массива. Единственная проблема заключалась в том, чтобы отслеживать присутствующие элементы, чтобы появился еще один std::set. Это наивный подход, если вы можете сказать мне что-то лучше.
- person shauryachats; 27.12.2014
std::set и std::map - это O (log n), так что это в первую очередь разрушает преимущество сортировки подсчетом. Вместо этого вы не можете использовать хэш-таблицы, потому что вам придется перебирать существующие элементы в отсортированном порядке. Но если вы можете сделать последнее, вам больше не нужно сортировать
- person Niklas B.; 27.12.2014
Согласно определению нотации Big-O, если мы говорим f(n) ∈ O(g(n)), это означает, что существует значение C > 0 и n = N такие, что f(n) < C*g(n), где C и N — константы. Ничего не сказано ни о значении C, ни о том, для какого n = N неравенство верно.
При любом анализе алгоритма необходимо учитывать стоимость каждой операции машины Тьюринга (сравнение, перемещение, суммирование и т. д.). Величина таких затрат является определяющим фактором того, насколько большими (или маленькими) должны быть значения C и N, чтобы неравенство стало истинным или ложным. Убрать эти затраты — наивное предположение, которое я сам делал во время курса анализа алгоритмов.
Утверждение «сортировка с подсчетом равна O(n+k)» на самом деле означает, что сортировка является полиномиальной и линейной для заданных C, n > N, n > K, где C, N и K — константы. Таким образом, другие алгоритмы могут иметь лучшую производительность для меньших входных данных, потому что неравенство верно только в том случае, если заданные условия верны.
