Confused о сложности подсчета сортировки алгоритма

Question

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

1. Как это только O(n) сложность? В алгоритме имеется 5 циклов. Должна ли сложность для каждого цикла быть 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]; 
} 

Answer 1

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

Пусть три «для» петли, что каждый работает в 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(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) и точно определить мой ответ на ваш вопрос: сложность алгоритма по-прежнему рассматривается как линейная.

Answer 2

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

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

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

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

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