1

配列Aで表される最大ヒープがあり、次の質問があります。

Is it possible to build a sorted list , based on the maximum 
heap - A - in O(n*log(log(n))) ? 

私の答え:いいえ、できません!いつでもAMergeSortin O(n*log(n)) またはQuickSortin O(n*log(n))(最悪の場合O(n^2))で実行して実行できます。

また、に基づいて実際のヒープを構築することも考えましたA。これには、が必要O(n)であり、そこからすべての要素を抽出しますがO(n*log(n))、ここでは何も得られませんでした。

現時点では、オプションが表示されませんO(n*log(log(n)))。アイデアはありますか?

4

2 に答える 2

6

不可能だと思います。o(n)に最大ヒープを構築するアルゴリズムがあります(ここを参照してください。最大ヒープを構築するO(n)アルゴリズムはありますか?)したがって、o(n)にヒープを作成できればn)次にo(n log(log(n))でソートすると、o(n log(log(n))で機能するソートアルゴリズムを取得できます。これは、初期情報がない場合は不可能です。入力。

于 2012-06-22T12:33:11.997 に答える
2

配列形式に最大ヒープがある場合、その配列に挿入ソートのようなものを使用すると、かなり良い結果が得られるはずです。配列形式の最大ヒープはほぼソート(降順)されており、配列がほぼソートされている場合の挿入の最適なケースはO(n)です。それでもO(n ^ 2)の最悪のケースがありますが、最悪のケースに遭遇したことはないと思います。

于 2012-06-22T14:43:06.680 に答える