私はアルゴリズム分析の試験の演習を行っていますが、これはそのうちの 1 つです。
n 個の要素 (比較可能) のリストを入力として取り、それらを O(n log m) 時間で並べ替えるアルゴリズムを提示します。ここで、m は入力リスト内の個別の値の数です。
一般的な並べ替えアルゴリズムについて読んだことがありますが、解決策が思いつきません。
ご協力いただきありがとうございます
質問する
872 次
1 に答える
8
n要素に対して拡張平衡二分探索木を構築できます。各ノードに保存されている拡張情報は、その頻度です。nツリーへの挿入を使用してこの構造を構築します。ノードO(n lg m)しかないため、これを行う時間は です。m次に、このツリーの順序どおりのトラバーサルを行います。左側のサブツリーにアクセスし、ルートf時間に格納されている要素を出力しfます。これは頻度です (これは拡張情報でした)。最後に右側のサブツリーにアクセスします。この走査には時間がかかりますO(n + m)。したがって、この単純な手順の実行時間O(n lg m + n + m) = O(n lg m)はm <= n.
于 2012-09-27T18:08:19.883 に答える