Почему подсчет сортировки не используется для больших входов?

Question

Счетная сортировка - это алгоритм сортировки со средней сложностью по времени O(n+K), а сортировочная сортировка предполагает, что каждый входной элемент является целым числом в диапазоне от 0 до K.

Почему мы не можем выполнить линейный поиск максимального значения в несортированном массиве, равного ему K, и, следовательно, применить к нему сортировку с учетом?

Answer 1

В случае, когда ваши входы являются массивами с 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

Answer 2

Вы задаетесь вопросом: почему сортировка не используется для больших входов?

Что мы делаем при подсчете сортировки? Мы берем другой массив (предположим, b[]) и инициализируем все элементы в ноль. Затем мы увеличиваем индекс, если этот индекс является элементом данного массива. Затем мы запускаем цикл от нижнего предела до верхнего предела данного массива и проверяем, равен ли элемент индекса моего взятого массива (b[]) 0 или нет. Если он не равен нулю, это означает, что индекс является элементом данного массива.

Теперь, если разница между этими двумя значениями (верхний предел и нижний предел) очень велика (например, 10^9 или более), то одного цикла достаточно, чтобы убить наш компьютер.:)

Answer 3

Согласно определению 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 являются постоянными. Таким образом, другие алгоритмы могут иметь лучшую производительность для меньших входных данных, поскольку неравенство истинно, только если заданные условия выполняются.