Подсчет-сортировка Big O - PullRequest
Новая
       9

Подсчет-сортировка Big O

0 голосов
/ 18 сентября 2018

Я пытаюсь выяснить большие нотации и придумаю стоимость и время для алгоритма сортировки подсчета, однако мой ответ кажется неправильным. Это то, что я получаю. 

                                   Cost           Time
Counting-sort(A,B, k)                 C1              1 
Let C[0...K] be a new array           C2              1
for i = 0 to k                        C3              K 
    C[i] = 0                          C4              K-1
for j=1 to A.length or n              C5              n
    C[A[j]] = C[A[j]] + 1             C6              n-1   
for i = 1 to k                        C7              K   
    C[i] = C[i] + C[i-1]              C8              K-1
for j=n or A.length down to 1         C9              n 
    B[C[A[j]] = A[j]                  C10             n-1  
    C[A[j]] = C[A[j]] -1              C11             n-1

Я получаю 4k + 4n -5, но вижу правильный ответ: 2k + 2n, то есть O (k + n), почему это неправильно?

...