特定の文字列の文字頻度を計算するための最も効率的な (時間と空間) アルゴリズムを探しています。
頭に浮かぶ最も単純なアルゴリズムは、検索するフラグ配列 (サイズ = 異なる文字の数) を用意し、対応するインデックスのカウンターをインクリメントすることです。これは線形時間で機能します。これに関する唯一の問題は、フラグ配列のスペース要件です。すべての ASCII 文字が必要な場合、最大 256 になる可能性があります。
スペース/時間を節約できるより良いアルゴリズムはありますか?
1288 次
1 に答える
3
ハッシュ テーブルを使用してカウンターを格納する場合、文字列内のさまざまな文字の数に比例するスペースが必要ですが、線形時間で計算を実行できます。各文字を少なくとも 1 回は見る必要があるため、線形時間よりも良い結果が得られないことは容易にわかります。
ただし、実際には、文字列が文字を格納するために実際に 1 バイトしか使用しない場合 (つまり、Unicode ではない場合)、「フラグ配列」は約 1 kb しかなく、(定数係数) ハッシュ テーブルの時間とスペースのオーバーヘッド。
于 2012-08-27T01:37:00.143 に答える