Продолжительность подсчета сортировки

Question

Я пытаюсь понять время выполнения подсчета сортировки. В своих записях он говорит, если предположить, что размер массива А равен п, а к есть число раз каждое число встречается,

Counting-Sort(A,k) { 
    for (i=1; i <= k; i++) // initialize number counters to 0 
     times[i] = 0; 

    for (j=1; j <= length[A]; j++) // decide how many times each 
     times[A[j]]++;     // number appears in the input 

    // form the sorted array 
    m=1; 
    for (i=1; i <= k; i++) // consider each number in the range 
     for (j=1; j <= times[ i ]; j++) { // generate that number in 
      A[m]=i;     // the output as many times as 
      m++;      // it occurs in the input 
     } 
    } 

Пусть T _я обозначает число раз внутренний цикл итерации для каждого i. Когда мы смотрим на вложенные циклы в нижней части кода, обратите внимание, что каждый раз, когда внутренний цикл повторяется, мы помещаем новый номер в его правильное место в выходном массиве. Следовательно: сумма t _i (от i = 1 до k) = n.

Я не понимаю, почему эта сумма равна n. Внешний цикл выполняет итерацию k раз, а внутренний цикл может повторяться не более n раз, поэтому он должен быть O (nk). Может кто-нибудь объяснить? Спасибо

Answer 1

Как вы можете видеть на петле

m=1; 
for (i=1; i <= k; i++) // consider each number in the range 
    for (j=1; j <= times[ i ]; j++) { // generate that number in 
     A[m]=i;     // the output as many times as 
     m++;      // it occurs in the input 
    } 

его сложность будет равна тому, сколько раз выполняется тело внутреннего цикла. Когда i = 1, выполняется times[1] раз, когда i = 2 =>times[2] раз, и так, когда , times[k] раз.Таким образом, общее внутреннее тело выполняется times[1] + times[2] + ... + times[k] раз, и эта сумма равна n, так как каждый элемент подсчитывается один раз.

Answer 2

Примечания не совсем правильные. k - это наибольшее число, которое отображается в вашем массиве (то есть оно имеет номера от 1 до k). Итак, давайте пошагово алгоритм:

1. Инициализировать k «закрома»: O(k)
2. графа, как часто происходит каждый номер: O(n)
   • Сумма значений во всех бункерах именно n, потому что вот сколько записей мы имели в общей сложности в массиве
3. перебрать закрома: O(k)
   • Установить как много элементов в массиве результатов, как бункер представляет собой: по-видимому O(n)

Важным здесь является то, что мы знаем, что даже если мы итерация над k бункерами и там могли, в общем случае, до n значений, представленных каждым бункером, мы устанавливаем бункеры так, чтобы во всех итерациях внешнего цикла внутренний цикл все еще выполнялся в сумме n раз. Следовательно, общая сложность этого шага фактически равна O(n).

Если мы проигнорируем наши дополнительные знания о содержимом корзин, вы абсолютно правы.

Теперь есть окончательный поворот: если k > n, это фактически в O(k), а не O(n)! Потому что теперь внешний цикл - это то, что «работает чаще».

Надеюсь, это имеет смысл.

Answer 3

Алгоритм

Подсчет Сортировка, известный также как гистограмме Сортировка

n = length of input Array 

k = number of unique symbols that appear in the input Array 

• Инициализация занимает k Время

• Подсчет принимает n время

• Перечисление занимает Sum { Count(i) } = n Время

Сложность

Time = k + n + n = 2n+k 

Time ~ O(2n+k) = O(n+k) 

Space = n + k ~ O(n+k)