問題タブ [clrs]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - 二次関数の漸近タイトバウンド
CLRS ( Cormen、Leiserson、Rivest、および Stein によるアルゴリズムの紹介) では、関数の
f ( n ) = an 2 + bn + c
彼らは言った
定数c 1 = a /4、c 2 = 7 a /4、およびn 0 = 2·max(| b |/ a , √(| c |/ a )) を取るとします。
次に、すべてのn ≥ n 0に対して 0 ≤ c 1 n 2 ≤ an 2 + bn + c ≤ c 2 n 2です。 したがって、 f ( n ) は Θ ( n 2 ) です。
しかし、彼らはこれらの定数の値がどのように得られたかを特定しませんでした?
証明しようとしましたができませんでした。
これらの定数の由来を教えてください。
algorithm - MAX-HEAPIFYの最悪のケース:「最悪のケースは、ツリーの最下位レベルがちょうど半分いっぱいになったときに発生します」
CLRS 、第3版、 155ページでは、MAX-HEAPIFYでは、
その理由は、この場合、Max-Heapifyが左側のサブツリーを「フロートダウン」する必要があるためだと思います。
しかし、私が得ることができなかったのは、「なぜ半分いっぱい」なのか?
Max-Heapifyは、左側のサブツリーにリーフが1つしかない場合にも、フロートダウンする可能性があります。では、これを最悪のケースと考えてみませんか?
algorithm - CLRS の Fibonacci Heap size(x) 分析には欠陥がありますか?
CLRS の Introduction to Algorithms 3rd edition P.525 で、サイズ (x) の下限を分析すると、「ノードに子を追加してもノードのサイズを減らすことができないため、Sk の値が増加するため」と引用した文があります。 k" で単調に。しかし実際には、Sk が k に対して単調に増加するとは限らないことを示す反例を示すことができると思います。次のグラフでは、key=1 のノードの次数は 2 で、次数が 2 のノードは他にありません。つまり、S2=8 です。同様に、S3=6である。しかし、現在、S3 は S2 より小さく、つまり、Sk は k に対して単調に増加していません。
ヒープは、一連のカットとカスケード カットを実行することにより、順不同の二項サブツリーから派生できます。
上記の構造が有効なフィボナッチ ヒープかどうかを知りたいです。もしそうなら、それは有効な反例でもあります。
algorithm - CLRSのユニバーサルハッシュの章を理解する
こんにちは私はCLRSのユニバーサルハッシュに関する章を読んでいます。
234ページ
系11.4
ユニバーサルハッシュとmスロットのテーブルをチェーンすることによる衝突解決を使用すると、O(m)INSERT操作を含むn個のINSERT、SEARCH、およびDELETE操作のシーケンスを処理するのにTheta(n)に予想時間がかかります。
ちょっとわかりましたが、この英語の文章を理解するのに苦労しています。「O(m)INSERT操作を含む」という終わりはどういう意味ですか?
n = O(m)の挿入がすでに実行されているという意味ですか。じゃあ……わかりません。この文を解析できません。1番目のINSERTと2番目のINSERTの違いは何ですか?
ご意見をお聞かせください。
ありがとう!
algorithm - 中央値選択アルゴリズム - 絶対中央値、または絶対中央値に近い「中央値の中央値」を見つけますか?
CLRS 第 3 版のセクション 9.3「最悪の場合の線形時間での選択」では、O のリストの中央値を見つけるための「選択」アルゴリズム (Blum、Floyd、Pratt、Rivest、および Tarjan のために BFPRT アルゴリズムと呼ばれることもあります) について説明しています。 (n) 最悪の場合の時間。ホワイトボードでサンプルを実行しようとしたとき、少し混乱しました。「Select」の呼び出しごとに特定の数の要素を削除できることを理解しています(30%が削除され、70%が再度チェックされる必要があると読んだことがあります)、私が混乱したのは、配列のどの部分を削除できるかでしたつまり、配列が高さ 5、幅 n/5 の行列として視覚化されている場合、では、排除された要素はどの象限にあるのでしょうか? 元々は対角線上に隣接する 2 つの象限だと思っていましたが、中央値の中央値によっては 1 つの象限にすぎないと考えています (手順 5、6、および 7 を参照)。ここで)。
そこで、ウィキペディアに行って、CLRS よりも分析が少ない簡単な説明があるかどうかを確認しました (分析のために CLRS に戻る前にアルゴリズムを理解するため)。私はこれに行き着きました、特に「最終的に、「中央値の中央値」がピボットとして選択されました。」ウィキペディアの説明の音から、「選択」は、クイックソートのピボットを選択する目的で十分な中央値である要素ではなく、真の中央値を見つけません。
では、真の中央値に関して「選択」は何をし、どのように行うのでしょうか? その中で思いつくのが「部分階層」という言葉で、それが理由で「選択」が機能するのだと理解していますが、この部分階層を元にリストから要素を中央値から除外するにはどのような論理が必要なのでしょうか。
algorithm - 最大フローのプッシュ再ラベルアルゴリズムで、ソース s からシンク t へのパスがないのはなぜですか?
CLRS から次の補題を理解するのが困難です。
G をフロー ネットワーク、s と t をソース ノードとシンク ノード、f を s から t へのプリフロー、h を G の高さ関数とします。この場合、残差グラフ G fには s から t への拡張パスはありません。 .
どうしてこれなの?
algorithm - ノードの平均深さがΘ(lg n)であるnノード二分探索木の高さに漸近的な上限を与える
最近、私はCLRSのすべての演習を解決しようとしています。しかし、私が理解できないものがいくつかあります。CLRS演習12.4-2からのそれらの1つは次のとおりです。
ツリー内のノードの平均深さがΘ(lg n)であるが、ツリーの高さがω(lg n)であるように、n個のノードで二分探索木を記述します。ノードの平均深さがΘ(lgn)であるnノード二分探索木の高さに漸近的な上限を与えます。
この問題を解決するためのアイデアや参考資料を誰かが共有できますか?ありがとう。
java - Hashtable の負荷係数が CLRS ブックに記載されているものと一致しないのはなぜですか?
Hashtableクラスに関するJavaのドキュメントから、それは言う
原則として、デフォルトの負荷係数 (.75) は、時間とスペースのコストの適切なトレードオフを提供します。
したがって、Hashtable の負荷係数は 0.75 です。つまり、N 個のキーがある場合、Hashtable は M = N/0.75 のスペースを使用してそれらを格納します。
CLRS ブックでは、ロード ファクター アルファも紹介されています。
しかし、私の理解では、CLRS はアルファを 1 よりも大きく設定することを意図しています。つまり、M = N/アルファ < N です。これは、ハッシュテーブルが M < N の場合に M スロットを使用できることを意味し、未使用のキーからストレージを節約できます。
通常、N の正確な値がわからないため、M < N はストレージを節約できると言いますが、キーのセットはわかっており、N を使用して可能なキーの数を表します。キーのセットは非常に大きいかもしれませんが、実際に使用されるキーの数は非常に少ないです。したがって、M を N より小さく設定すると、ストレージを節約できます。また、これが通常、Hashtable がすべての {key, value} を 1:1 でマップするために直接配列を使用しない理由です。
しかし、Java の Hashtable は N を超えるストレージを使用します。これは CLRS の設計と一致していないと思いますよね?
私は正しいですか?
ありがとう
algorithm - クイックソートと挿入ソートのハイブリッド予想実行時間
私はCLRS第3版を独学で学んでいます。これは、すべての人へのサービスとしての回答とともに、私が遭遇した難しい質問の1つです。
7.4-5
入力が「ほぼ」ソートされている場合の挿入ソートの高速実行時間を利用することで、実際のクイックソートの実行時間を改善できます。k
要素が少ないサブアレイでクイックソートを呼び出すときは、サブアレイをソートせずに単純に戻るようにします。クイックソートのトップレベルの呼び出しが戻った後、配列全体で挿入ソートを実行して、ソートプロセスを終了します。O(nk+nlg(n/k))
この並べ替えアルゴリズムは予想される時間内に実行されると主張します。k
理論的にも実際的にも、どのように選ぶべきでしょうか?
algorithm - グラフ - 有向グラフの二乗
はい、これは宿題になります (私は大学のためではなく独学です) 質問ですが、解決策を求めているわけではありません。代わりに、質問自体を明確にしたいと考えています。
CLRS第 3 版、593 ページ、物品税 22.1-5、
有向グラフ G = (V, E) の 2 乗はグラフ G 2 = (V, E 2 )であり、G がu の間に最大で 2 つのエッジを持つパスを含む場合にのみ、(u,v) ∈ E 2となります。と v。G の隣接リスト表現と隣接行列表現の両方について、G からG 2を計算するための効率的なアルゴリズムを説明してください。アルゴリズムの実行時間を解析してください。
ただし、CLRS の第 2 版 (本のリンクが見つかりません) の 530 ページでは、同じ演習ですが、説明が少し異なります。
有向グラフ G = (V, E) の 2 乗はグラフ G 2 = (V, E 2 ) であり、(u,w) ∈ E 2は、ある v ∈ V に対して両方の (u,v ) ∈ E および (v,w) ∈ E.つまり、Gが u と wの間にちょうど 2 つのエッジを持つパスを含むときはいつでも、G 2 は u と w の間にエッジを含みます。G の隣接リスト表現と隣接行列表現の両方について、G からG 2を計算するための効率的なアルゴリズムを説明してください。アルゴリズムの実行時間を解析してください。
「正確に2つのエッジ」を使用した古い演習については、理解して解決できます。たとえば、adjacency-list の場合、v->neighbour->neighbour.neighbour を実行し、(v, neighbour.neighbour) を新しい E 2に追加します。
しかし、「最大で 2 つのエッジ」を使用する新しい演習については、私は混乱しています。
「G に u と v の間に最大で 2 つのエッジがあるパスが含まれている場合のみ」とはどういう意味ですか?
1 つのエッジが「最大で 2 つのエッジ」という条件を満たすことができるため、u と v が 1 つのエッジのみを含むパスを 1 つしか持たない場合、E 2に (u, v) を追加する必要がありますか?
u と v に 2 つのエッジを持つパスがあり、3 つのエッジを持つ別のパスもある場合、 (u, v) を E 2に追加できますか?