問題タブ [clrs]

MATLAB でヒープ ソート関数を作成しましたが、正常に動作しますが、入力の長さが 1000 以上の場合、長い時間がかかる場合があります(たとえば、長さが 1000 の場合は 0.5 秒かかります)。MATLAB がヒープ ソート アルゴリズムで非常に高速に実行されないのか、コードを改善する必要があるだけなのかはわかりません。私のコードを以下に示します。

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%％

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%％

a(n+1-i) = [];おそらく、多くの時間を消費するコードであることは承知しています。しかし、（入力ベクトルの任意の数よりも小さい）に変更すると、[]役に立た-999ず、さらに時間がかかりました。

私はCLRSの本に従っており、Pythonですべてのアルゴリズムを実装しています。これはマージソートアルゴリズムです。テスト配列でマージ関数をテストしたところ、動作するため、merge_sort 関数である必要がありますが、本の疑似コードとほとんど同じです。

私は通常、マスター定理の 2 つのバージョンを見てきました。

バージョン 1:

(ティム・ラフガーデンのコースより)

フォームの再帰関係については、

3つのケースがあり、

バージョン 2:

( CLRSより)

フォームの再帰関係については、

3 つのケースがあります。

質問: どちらのバージョンを優先すべきですか? その理由は?

これは、配列内の線形検索の擬似コードであり、配列内iの目的の要素が見つかった場合はインデックスを返し、そうでない場合はインデックスを返します (これは CLRS ブック、第 3 版、演習 2.1-3 からのものです)。eANIL

私はそこからループ不変式を推定しようとしているので、私の理解によれば、ループ内の任意の時点で、サブ配列A[1..i-1]には等値テストが偽であることが証明された値のみが含まれているという事実によって表されると思います。

具体的には、サブ配列の長さが null であることを意味する最初の反復の前に、そのような要素がそれに属するi-1 == 0ことはできません。次の反復の前に、等価テストも終了条件でもあるため、想定される不変プロパティは依然として true を保持する必要があります。そうでない場合、ループは既に終了しています。終了時に、関数がインデックスを返そうとしている (その場合、ループ不変条件は自明に true である) か、NIL が返されている (その場合、ループ不変条件は any に対して true を保持する) のいずれかです。vv == ei == A.length + 11 < j < i

上記は正しいですか？そうでない場合に備えて、正しいループ不変式を提供していただけますか?

ご清聴ありがとうございました。

この問題を解決しようとしています (CLRS、第 3 版、演習 11.2-1):

ハッシュ関数 h を使用して、n 個の異なるキーを長さ m の配列にハッシュするとします。単純な一様ハッシュを仮定すると、予想される衝突の数は?

正解は n(n-1)/2m です。これは、CLRS のインストラクターのマニュアルから取得されます。

私の解決策は次のとおりです。

• キー 1 の挿入の場合: 先行キーとの予想衝突数 = 0

• キー 2 の挿入の場合: 先行キーとの予想衝突数 = 1/m

• キー 3 の挿入の場合: 前任者との予想衝突数 = 1/m*(1/m) + (m-1)/m*(2/m) = (2m-1)/m^2

私の推論: 1 つのスロットでキー 1 と 2 が衝突する確率は 1/m です。つまり、キー 3 の衝突の確率は 1/m です。キー 1 とキー 2 が衝突しなかった可能性は (m-1)/m あります。つまり、それらは異なるスロットにあり、キー 3 の衝突の確率は 2/m です。

期待の線形性による 3 つのキーの衝突の期待数 = 0 + 1/m + (2m-1)/m^2 = (3m-1)/m^2

CLRS によると、3 つのキーの予想衝突数は 3/m である必要があります。

インディケータ RV を使用して正しい解を見つける方法を知っています。

私の質問は次のとおりです。ソリューションのどこで間違いを犯しましたか? なぜ違うのですか？

CLRS ブックからの完全な k-ary ツリーの次の定義を検討してください。

定義:完全なk 分木とは、すべての葉の深さが同じで、すべての内部ノードの次数がkであるk分木です。(p.1179)

この定義により、次の二分木は完全であると考えます

CLRS 完成二分木

しかし、完全なツリー (完全な二分木、k分木の特定のケース) のこの回答定義に基づいて、

おそらく最も深いレベルを除いて、すべてのレベルが完全に埋められている二分木。深さn (ツリーの高さ) では、すべてのノードをできるだけ左に配置する必要があります。

これは、グリマルディの離散数学の本 (p. 601) にあるものと同じです。以下の根付き木は完全な木です。

完成した二分木

しかし、これは CLRS の定義には当てはまりません。なぜなら、Gは他のものと同じレベルにないからです。両方の定義のどちらが最もよく使用され、ケースに適していますか?

アルゴリズムの紹介で大きなOの定義を読みましたが、この本では私の混乱については触れられていません。

その定義によれば、関数 T(n) = 3n が O(n) に属していることは誰もが知っています。私の混乱は、O(n) に属するすべての関数が O(n^2) および O(n^3) に属しているかどうかです。および O(n^4) および O(n^k) k>1。これは、大きな O が上限を表すためです。0<=3n<= を満たす正の整数定数 c と正の整数定数 n0 を見つけることができます。 cn^2 n>=n0 の場合、答えが YES の場合、T(n) = 3n の定義が深刻な場合、O(n) を使用して T(n) = 3n を記述することを好むのはなぜですか?

さらに、これらの表記法 (ビッグ オー、ビッグ シータ、ビッグ オメガ) は、他の数学分野でどこで使用されていますか?

必要な参考文献またはこれについて述べている他の本を投稿してください

この質問のアルゴリズムを誰か教えてもらえますか? Q.挿入ソートは次のように再帰的な手続きで表現できます。A[1..n] をソートするために、A[1..n−1] を再帰的にソートし、ソートされた配列 A[1..n−1] に A[n] を挿入します。この再帰バージョンの挿入ソートの実行時間の再帰を記述します。

このアルゴリズムでは、8 回の乗算と 4 回の加算が時間の複雑さで使用されることを理解しています。

乗算はすべてのn/2 * n/2行列で行われます。これについていくつか質問があります：

1. を実行することで、最終的にすべてのn * nマトリックスのn=1サイズが縮小されT(n/2)ますか? その場合、以下の行列を返すのa11*b11と同じように、返すことは無意味に思えます。1*6a11*b11

次に、基本ケースはn==2else部分を実行する必要があります。これは、以下の操作が正当であるように思われるためです。

2. 足し算の部分がなぜかかっているの0(n^2)ですか？2 * 2つまり、すべての行列が以下のように縮小されるため、行列の加算ではなく単なる数値を扱っているということです。

では、加算部分は 4 だけ貢献する必要がありますか? （なぜ0(n^2)？）