Смущен сложностью алгоритма подсчета сортировки

У меня есть два сомнения по поводу алгоритма сортировки подсчетом:

  1. Как сложность только O(n)? В алгоритме 5 циклов for. Должна ли сложность каждого цикла for быть равна n? Итак, результат n^4 сложности? Я знаю, что ошибаюсь, и сортировка подсчета линейна, но я хочу знать, почему мои рассуждения неверны.

  2. Если алгоритм сортировки подсчетом является линейным, почему он O(n+K), а не только O(n), если добавить K, он больше не будет линейным, верно?

Я также имею в виду код сортировки подсчета:

void countSort(char *str)
{
    // The output character array that will have sorted str
    char output[strlen(str)];

    // Create a count array to store count of inidividul characters and
    // initialize count array as 0
    int count[RANGE + 1], i;
    memset(count, 0, sizeof(count));

    // Store count of each character
    for(i = 0; str[i]; ++i)
        ++count[str[i]];

    // Change count[i] so that count[i] now contains actual position of
    // this character in output array
    for (i = 1; i <= RANGE; ++i)
        count[i] += count[i-1];

    // Build the output character array
    for (i = 0; str[i]; ++i)
    {
        output[count[str[i]]-1] = str[i];
        --count[str[i]];
    }

    // Copy the output array to str, so that str now
    // contains sorted characters
    for (i = 0; str[i]; ++i)
        str[i] = output[i];
}

c counting-sort
person Brandon    schedule 04.02.2016    source источник
comment
Циклы не вложенные.   -  person Martin James    schedule 04.02.2016

Ответы (2)


arrow_upward
3
arrow_downward

Чтобы ответить 1:

Пусть есть три цикла for, каждый из которых работает в O(n), поэтому общая сложность составляет:

O(n)+O(n)+O(n) = O(n+n+n) = O(3n)

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

Чтобы ответить 2:

алгоритм зависит не только от размера N массива, но и от диапазона K собранных в нем чисел. для этого потребуется больший счетный массив и, следовательно, итерации для подсчета сортировки массива:

{1,10000000,3,2,0} // K=10000001

чем было бы:

{1,4,5,2,3} // K=6

поэтому сложность цикла for, используемого вашим кодом, рассчитывается следующим образом:

for(i = 0; str[i]; ++i) // O(n)

for (i = 1; i <= RANGE; ++i) // O(k)

for (i = 0; str[i]; ++i) // O(n)

for (i = 0; str[i]; ++i) // O(n)

и общая сложность такая же, как у O(n)+O(n)+O(n)+O(k) = O(n+k), и чтобы уточнить мой ответ на ваш вопрос: сложность алгоритма по-прежнему рассматривается как линейная.

person HazirBot    schedule 04.02.2016
comment
@martinkunev Я решил проигнорировать функцию memset(), потому что это не часть алгоритма, а часть реализации на C. Также она принимает RANGE+1 в качестве аргумента размера и, таким образом, вычисляет O(k). - person HazirBot; 05.02.2016

arrow_upward
1
arrow_downward

Асимптотическая сложность в некотором смысле показывает количество операций в зависимости от размера входных данных. Это полезно, потому что показывает, насколько алгоритм замедляется по мере увеличения размера входных данных. Константы не влияют на замедление, поэтому игнорируются. Игнорируя константы, получаем:

strlen(str) выполняет strlen(str) операций (просматривает всю строку, пока не найдет '\0')
memset() выполняет strlen(str) операций
вторая for выполняет RANGE операций
каждая из трех остальных fors делает strlen(str) количество операций

В вашем примере strlen(str) обозначается n, а RANGE - K. Таким образом, вся функция выполняет O(5n + K) = O(n + K) операций.

n + K по-прежнему является линейной функцией, будь то двух переменных (это полином степени 1).

Чтобы глубже понять это, вам нужно больше узнать об асимптотической сложности (строгой математической теории).

person martinkunev    schedule 04.02.2016