ソートの最悪、最善および平均時間の計算複雑度は、O(n+k)です。ここで、nはソートする要素の数です。 kとは何ですか？さまざまな定義があります。最大要素、最大要素と最小要素の差などです。カウントソートO（n + k）時間の複雑度でkとは何ですか？
arr1 [1, 3, 5, 9, 12, 7 ]とarr2 [1,2,3,2,1,2,4,1,3,2] arr1とarr2ためk何ですか？n < kは（要素値をソートする 要素の数よりも広い範囲がありますか？kキーの範囲であるので、計数ソートとarr1をソートする愚かであること本当、配列スロットの数、すなわち、それはこのように数字、Max-Min+1の場合。すべての可能な値をカバーするのにかかる。もちろん、これはあなたがMin最初のスロットとMax最後を割り当てることによって、スペースを無駄にしないことを前提としています。
それアポップですkがnの小さな倍数を超えていないときにカウントソートを使用しようとすると、n.kは、この場合のようにn.kがn.log nになることがあります。
ありがとう！ 3つの要素の配列[3、20、57] k = 3（3つの可能な値があります。 、ちょうど3 "アレイスロット"）またはk = 55（57 - 3 + 1）？ P.S.私はk >> nということを理解していますので、基数ソートを使います。ソートの計算には使用しません。 –
@CodeComplete： 'k
kは、アレイ内の可能な最大値であり、この例kは最初のk個のカウントのアレイがゼロにされる9
知識を共有していただきありがとうございます！私はあなたの答えを正しく得ましたか？3要素の配列[3、20、57] k = 57（ "kは配列の最大値です"）？右？ –
@ code-completeはい、あなたの例ではk = 57 – Farnabaz
に等しく、各番号は、0と9の間の整数であり、長さ5の配列を有すると仮定する。その後、配列内のn個の要素が読み込まれ、n個の要素の値に応じてk個の要素がインクリメントされます。カウントソートの出力パスでは、k個のカウントの配列が読み込まれ、n個の要素の配列が書き込まれます。したがって、k個の書き込み（カウントをゼロにする）、n回の読み出し、k回の読み出しとn回の書き込み（合計2n + 2k回の操作）がありますが、大きなOは定数2を無視するので、時間の複雑さはO（n + k）です。
ソート時間の複雑さを計算するのがO（n + k）ならば、nはソートするすべての要素の数であり、kは数ですDISTINCT要素？例えば、配列[3,5,7,5,1,5]の場合、n = 6、k = 4？ –
@CodeComplete - 通常、kは数値の範囲で、最大値+ 1 - 最小値です。カウント配列のサイズはkです。 [3 5 7 5 1 5]では、kは7（最大値は7 + 1 - minの値1）です。 – rcgldr
"そんなに"あるとは思わない。 –
おそらく、「n> k」のためではなく「n
どのようにコード化したかによって異なります。あなたは非常に簡単に自分自身を把握できるようにする必要がありますので、アルゴリズムをルックアップするか、時間の複雑さの基礎を見直したいかもしれません。これは本質的に[アルゴリズムの時間複雑性を見つける方法]（https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm）の複製です。 – Dukeling