問題タブ [clrs]

答えを探している問題は次のとおりです。

配列 A[1...n] には、1 つを除く 0 から n までのすべての整数が含まれます。補助配列 B[0...n] を使用して A に出現する数値を記録することにより、欠落している整数を O(n) 時間で簡単に特定できます。ただし、この問題では、A の整数全体にアクセスすることはできません。 1回の操作で。A の要素は 2 進数で表され、それらにアクセスするために使用できる操作は「A[i] の j 番目のビットをフェッチする」ことだけで、これには一定の時間がかかります。この演算だけを使用しても、不足している整数を O(n) 時間で決定できることを示してください。

私はこのアプローチを念頭に置いています。上記のフェッチ制限がなければ、すべての数値を取得してそれらの XOR を一緒に実行したでしょう。次に、結果を 1..n のすべての数値で XOR します。そして、この結果が私の答えになります。この問題では、同様に、配列内のすべての要素について、log(n+1) ビットの距離にある異なる数のビットを繰り返し XOR し、要素 1...n と XOR することができますが、複雑さは次のようになります。私の意見では O(nlogn) です。

O(n) の複雑さを達成する方法は? ありがとう

私は CLRS を読んでいて、50% の確率で 0 または 1 を生成するプロシージャ Rand(0,1) を使用して、a から b の間の乱数を一様ランダムに生成するプロシージャ Rand(a,b) を作成するという問題に遭遇しました。 .

私は次の解決策を考えました。これは時間的に O(b) です。

これに対するより良いアプローチを提案してください。

空の B ツリーに 3 つの 4 を挿入しようとしています。t = 3. オンラインでいくつかのアプレットを試してみましたが、4 を 1 回挿入してから 4 をドロップするだけで済みました。疑似コードを完全には理解していないため、CLRS で実装されている方法ですか。

今、私はアルゴリズムの紹介、クイックソートの章を読んでいました。末尾再帰を最適化に使用できるとのことでした。

ただし、上記のコードのスタックの深さは、反復ごとにピボット番号が [1,n-1] [n] の場合、O(n) になります。

上記のコードで私が理解しているのは、最初に長さが短い部分配列を処理するということです。しかし、なぜ O(lgn) に還元できるのでしょうか? ピボットがまだ [1,n-1] [n] である場合、O(n) スタックの深さを維持していると思います。

私はCLRSを読んでいますが、ヒープソートは

MAX_HAPIFY はO(lg n). この本には、MAX-HAPIFYn回実行すると書かれているので、O(n lg n)時間です。

しかし、ヒープのサイズが反復ごとに 1 ずつ縮小している場合、そうではありませんO(lg n!)か?

ですlg 1 + lg 2 ... + lg(n-1) + lg (n) = lg(n!)よね？

私はCLRSを読んでいて、「フィボナッチヒープの遅延は可能な限り長く機能します」という行に出くわしました。

ハフマン コーディング アルゴリズムには、次の補題があります。

最適なバイナリ プレフィックス コードに対応するバイナリ ツリーがいっぱいです

しかし、理由がわかりません。この補題をどのように証明できますか?