問題タブ [clrs]

この問題に可能な貪欲なアルゴリズムはありますか。私はそのための DP アルゴリズムを作成しましたが、貪欲なアルゴリズムについては確信が持てません。貪欲なアルゴリズムが存在するかどうかを説明してください。

問題に精通していない人のために：

a1 から an までの 'n' 個のアクティビティがあります。各活動 ai には、関連する開始時刻 si と終了時刻 fi [si,fi) があります。各アクティビティ ai には、それに関連付けられた値 vi もあります。2 つのアクティビティが同時に発生することはありません。タスクは、相互に互換性のあるアクティビティを選択して、合計値、つまりスケジュールされたすべてのアクティビティの合計を最大化することです。相互に互換性があるとは、実行時間が重複しないことを意味します。

それを証明する必要がある CLRS からの質問を解決しています (ceil(lg lg n))! は多項式で有界です。

theta(lg n)=o(n) を証明できれば

私が直面している唯一の問題は、theta(lg n)=o(n)であることを証明することです。助けてください！

本 CLRS の 69 ページで、nC2 は単位分割統治法 (U - 4) の Θ(n^2) であると述べられています。この結果がどのように真実であるかを説明できる人はいますか?

それで、ごく最近、好奇心から、CLRS の「Introduction to Algorithms」という本を購入しました。この本を読み始めたとき、本にあるいくつかの非常に典型的なアルゴリズムが非常に異なる方法で実装されていることに気付きました。

CLRS でのクイックソートの実装は、一般的な Hoare のクイックソートのアルゴリズムとは大きく異なります。

だから私の質問に来て...

Robert Sedgewick がアルゴリズムに関する Coursera コースで使用したコードです。

対照的に、CLRS で提供される挿入ソートの実装は、

これについてかなり奇妙なのは、実行時間です。2 つの異なる実装を実行したときの結果は次のとおりです。

配列の要素数: 10,000

Robert Sedgewick の実装にかかった時間: 0.235926 秒

CLRS の実装にかかる時間: 0.078608 秒

誰か私にこれらの結果を説明してもらえますか? アルゴリズムはほとんど同じです。実装のみが異なります。実装のわずかな違いが、実行時間にこれほど大きな違いをもたらすのはなぜでしょうか?

以下は、CLRS によるアルゴリズム入門のテキストです。以下は、有限状態オートマトンを使用した文字列照合のコード スニペットです。Trnstion 関数を使用して、検索するパターンで状態テーブルを作成します。

遷移関数の計算: 次の手順は、与えられたパターン P [1: :m] から遷移関数 sigma を計算します。

この手順は、式 (32.4) の定義に従って簡単な方法で sigma(q, a) を計算します。2 行目と 3 行目で始まるネストされたループは、すべての状態 q とすべての文字 a を考慮し、4 ～ 8 行目で sigma(q, a) を Pk がサフィックス Pqa となるような最大の k に設定します。コードは、考えられる最大の k 値である min(m, q+1) から始まります。次に、P0 がすべての文字列の接尾辞である空の文字列であるため、Pk が接尾辞 Pqa になるまで k を減らします。これは最終的に発生する必要があります。

上記のコードに関する私の質問

1. 4 行目で k を min(m + 1, q+2) として選択しているのはなぜですか?

2. 以下の説明文の著者は、「コードは、考えられる最大の k の値である min(m, q+1) で始まる」と述べています。上記の 4 行目の疑似コードと一致しないのはどれですか?

上記の質問に答えながら、疑似コードの簡単な例と手順を説明するように要求します。

第 24 章の DIJKSTRA 疑似コード 658 ページの CLRS 第 3 版では、内側のループで、新しく追加された頂点から隣接するエッジを緩和しながら、キューから既にデキューされ、ツリーへの最短パスに追加されたエッジで緩和が許可されるのはなぜですか?

内側のループが、頂点が既に最短パス ツリーの一部であるかどうかを確認しないのはなぜですか。

正しいアプローチはどれですか？

アルゴリズムの最悪の場合の時間の複雑さとその上限との関係/違いは何ですか?