2

「Programming Pearls」を読んでいましたが、解決策の説明の 1 つで本当に混乱しています。

質問は次のとおりです。「最大 n 個の正の整数を含むファイルで、それぞれが n 未満で、n = 10^7 です。各正の整数は最大 10 回出現する可能性があります。ファイルをどのように並べ替えますか?」

本で与えられた解決策: "各整数が最大 10 回出現する場合、4 ビットのハーフバイトでその出現を数えることができます。問題 5 (下記) の解決策を使用して、完全なファイルを 1 回のパスで並べ替えることができます。 10,000,000/2 バイト、または 10,000,000/2k バイトの k パス」

問題 5の解決策: 2 パス アルゴリズムは、最初に 5,000,000/8 = 625,000 ワードのストレージを使用して整数 0 ～ 4,999,999 を並べ替え、次に 2 番目のパスで 5,000,000 ～ 9,999,999 を並べ替えます。k-pass アルゴリズムは、時間 kn および空間 n/k で n 未満の最大 n 個の繰り返されない正の整数をソートします。)

著者がどのようにして 10,000,000/2k のスペースをソートするのかわかりません。つまり、問題 5 の解決策に基づいて、最初のパスでソートするために 625K バイトのスペースと、カウントを格納するために整数ごとに追加の 1/2 バイトが必要ですよね?

誰かがこれを理解するのを手伝ってくれませんか?

どうもありがとう。

4

2 に答える 2

1 
Each positive integer could appear at most ten times.

これには、2 バイトではなく、カウンターごとに 4 ビットを使用できます。カウンターをグループ化すると、この値をさらに下げることができます。たとえば、3 つのカウンターをグループ化すると、10*10*10=1000 の組み合わせになり、そのためには 10 ビット (=1024 値) が必要になります。

于 2011-08-28T07:44:42.170 に答える
0

10,000,000 - 可能な値が 10,000,000 あるためです。

2 - 各バイトは 2 つのハーフバイトで構成されているためです。

于 2011-08-28T07:45:05.180 に答える