問題タブ [clrs]

CLRS 演習: 6.5-8

この操作は、 node の項目をheap からHEAP-DELETE(A,i)削除します。n 要素の最大ヒープに間に合うように実行される の実装を提供します。iAHEAP-DELETEO(lg n)

A[10]={84,22,19,21,3,10,6,5,20}入力（インデックスは1から始まる）とA[6]=10削除されたアルゴリズムが間違っているのだろうか。最後のノードを で置き換えると、A[6]ヒープ プロパティに違反し、親の値が見落とされます。

このためのアルゴリズムを作成しましたが、それが正しく機能するかどうか、またはどこが間違っているかを知りたいと思いました。

最大サブアレイ問題 (clrs 4.1-2) のブルート メソッドを実装しようとしていましたが、次のように (非常に簡単に) 取得したと思いました:
PSEUDO-CODE:

しかし、それが返す要素が 1 つだけの場合に問題が発生する(from = to)ため、 の場合を考慮する必要がありますfrom = toが、これには有用なケースが除外されるか、冗長なケースが含まれます。

例 :
入力が 1,-4,3,-4 の場合、間違った答えが返されます (3 番目の要素である 3 のみなど)。
どんな助けでも感謝します。
月

編集: 1) 日が A.length に変更されました2)最大値が で
ある場合の処理​​方法を知りたかったのです。 3)疑似コードの行番号 5 に変更されました。from = tosum
0sum

CLRSアルゴリズムブックから次の問題が与えられました。

次の表の各関数 f (n) と時間 t について、問題を解くアルゴリズムが f(n) マイクロ秒かかると仮定して、時間 t で解くことができる問題の最大サイズ n を決定します。

1. 時間が 1 秒のとき、f(n)=nlog(n) の n をどのように計算できますか?
2. f(n)=n の n をどのように計算できますか! 1秒はいつ？

二分探索木に対して、n個の同一の入力がある場合を考えてみましょう。ノードを挿入する際に、 x.leftとx.rightからランダムに選択します。

clrs (12-1-(d)) には、このセットアップの予想実行時間を導き出すよう求める質問があります。直観的に、答えは単純に O(n lg n) です。しかし、どうやってそれを証明するのですか？

アドバイスをいただければ幸いです。

月。

clrs book からキューを実装しようとしていますが、期待どおりに機能していません。コードの何が問題になっていますか?

キューのサイズまたはエンキュー操作に問題がある可能性がありますか?

ただし、キューでのエンキュー操作が期待どおりに機能していないことは明らかです。これが私のコードです：