問題タブ [divide-and-conquer]

重複の可能性:
Java: マルチスレッドによるクイックソートの並列化

ここで悪い質問を作成して本当に申し訳ありません。間違いを繰り返したくありません。分割統治アルゴリズムで並列処理を実装する方法について書かれている記事を見つけました。マルチスレッドは、Parallel.Invoke メソッドを使用して実装されます。問題は、Java でこの構文を実装し、スレッドが CPU で動作するように最適化する方法です。

ここにC＃のサンプルがあります

そしてJavaで

次の問題は、アルゴリズムの問​​題（問題653）から抜粋したものです。

数のanx2行列が与えられます。配列のどちらの列にも⌈√n.⌉より長いサブシーケンス（連続する配列要素で構成されていない可能性がある）が含まれないように、配列内の行を並べ替えるO（n log n）アルゴリズムを見つけます。

これを解決する方法がわかりません。ある種の分割統治法の繰り返しを使うかもしれないと思いますが、見つけられないようです。

誰かがこれを解決する方法について何かアイデアがありますか？

配列は、その要素の値が 0 番目のインデックスから ( k -1) インデックスまで増加するように与えられます。kで値は最小になり、n番目の要素を通じて再び増加し始めます。最小要素を見つけます。

基本的に、ソートされた 1 つのリストが別のリストに追加されます。例: (1, 2, 3, 4, 0 , 1, 2, 3)。

私は最小ヒープの構築、クイック選択、単純なトラバースなど、あらゆる種類のアルゴリズムを試しました。しかし、O(n)以下にはなりません。しかし、この配列にはパターンがあり、バイナリ検索のようなものが可能であることを示唆し、複雑さは O(log n) のようなものである必要がありますが、何も見つかりません。考え??

ありがとう

T(n) = 2T(n/2) + log n を解こうとしています

置換 n = 2^k

したがって、基本的には i*2^i の項を合計する必要があります。ここで、i = 1 で n - 1 をログに記録します
。これらの項を合計する簡単な方法を見つけることができませんでした。私は何か間違っていますか？この再帰を解決する他の方法はありますか? マスター定理は彼女に効くでしょうか? はいの場合、どのように？

ありがとう。

問題の解決策を見つけるのに非常に大きな問題があります。整数の配列内の要素の最長の非減少サブシーケンスの長さを計算する、再帰的な分割統治アルゴリズムを作成する必要があります。次のコードがありますが、実際には機能していません。助けていただければ幸いです!!!

練習問題を解いていて、次の問題に出くわしました

以下の分割統治アルゴリズムに対応する繰り返しを書き留め、分割、征服、および結合のそれぞれのコンポーネントを正確にラベル付けします。

私の答えの試み。

1. T(n) を Foo が p から r に渡って行った作業とすると、T(n) は Foo(p, r) と同等になります。ここで、n は r - p + 1 です。

2. 次の繰り返しを取得します T(n) = T(n - 1) + Θ(n) + Θ(1)

3. 分割部分は、r-1 操作に対応する定数 Θ(1) になります。

4. 征服部分は、サブ問題を再帰的に解決する T(n - 1) です。

5. 結合部分は、T(n - 1) * s の乗算演算の定数 Θ(1) です。

しかし、私は Θ(n) について言及しなかったので、それは間違っているようです。行 6、7 の Θ(n) は、分割、征服、結合のどの部分に該当しますか?

木の分割統治アルゴリズムを書こうとしています。分割ステップでは、ノードを削除することにより、n個のノードとm個のエッジを持つ特定の無向グラフG =（V、E）をサブツリーに分割するアルゴリズムが必要です。すべてのサブグラフには、 n / 2を超えるノードが含まれないというプロパティが必要です（ツリーは可能な限り均等に分割する必要があります）。最初に、ツリーからすべての葉を再帰的に削除して最後に残っているノードを見つけようとしました。次に、Gで最長のパスを見つけて、その中央のノードを削除しようとしました。以下のグラフは、両方のアプローチが機能しないことを示しています。

私が望むことを実行するいくつかの動作するアルゴリズムはありますか（上記の場合はノードHを返します）。

任意の整数の乗法的分割を計算するための効率的なアルゴリズムを探しています。たとえば、12のそのようなパーティションの数は4であり、

12 = 12 x 1 = 4 x 3 = 2 x 2 x 3 = 2 x 6

私はこれについてウィキペディアの記事を読みましたが、それは実際にはパーティションを生成するためのアルゴリズムを私に与えません（それはそのようなパーティションの数についてのみ話します、そして正直なところ、それは私にはあまり明確ではありません！） 。

私が見ている問題では、非常に大きな数（> 10億）の乗法的分割を計算する必要があるため、動的計画法のアプローチを考え出そうとしていました（これにより、少数の可能なすべてのパーティションを見つけることができます。その小さい数自体が大きい数の要因である場合に再利用されます）が、これまでのところ、どこから始めればよいのかわかりません！

どんなアイデア/ヒントもいただければ幸いです。これは宿題の問題ではなく、とても面白そうなので、私が解決しようとしていることです。

Divide and Conquer アルゴリズムの Time Complexity を理解するのを手伝ってくれませんか。

これを例に取りましょう。 http://www.geeksforgeeks.org/archives/4583方法 2: T(n) = 3/2n -2 が得られましたが、その理由がわかりません。

申し訳ありませんが、開くための余分なページを提供した場合でも、そのようなアルゴリズムの複雑さを自分で見つけることができるように、少なくとも高いレベルまで理解したいと思っています。答えていただければ幸いです。

ある試験で、二分探索は分割統治アルゴリズムかどうか尋ねられました。私の答えはイエスでした。なぜなら、結果に到達するまで、問題をより小さなサブ問題に分割したからです。

しかし、試験官は、征服の部分はどこにあるのかと尋ねましたが、私は答えることができませんでした. 彼らはまた、それが実際には分割統治アルゴリズムであることを認めませんでした。

しかし、私がウェブ上でどこに行っても、そうであると書かれているので、その理由と、その征服部分がどこにあるのか知りたいです?