4

ソートカウントの実行時間を理解しようとしています。私のメモでは、配列Aのサイズがnであり、kが各数値の発生回数であると仮定すると、

 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は、各iに対して内部ループが繰り返される回数を示します。コードの下部にあるネストされたforループを見ると、内側のループが繰り返されるたびに、出力配列の正しい場所に新しい数値が配置されていることに注意してください。したがって、合計t i（i = 1からkまで）=n。

この合計がnに等しい理由がわかりません。外側のループはk回繰り返され、内側のループは最大n回繰り返される可能性があるため、O（nk）である必要があります。誰かが説明できますか？ありがとう

4

3 に答える 3

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)
于 2013-03-22T07:15:48.223 に答える
0

メモは完全に正しいわけではありません。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)ます！なぜなら、外側のループは「より頻繁に実行される」ものだからです。

これが理にかなっていることを願っています。

于 2013-03-21T13:21:46.377 に答える
0

あなたがループのために見ることができるように

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]回の場合、およびの場合i = k、times[k]回実行されます。したがって、内部本体の合計は実行回数になり、各要素が1回カウントされるtimes[1] + times[2] + ... + times[k]ため、その合計はに等しくなります。n

于 2013-03-21T15:51:19.127 に答える