問題タブ [divide-and-conquer]

FFT を使用した分割統治アルゴリズムによって多項式 A(x) を評価しようとしています。基本的に、多項式を奇数根と偶数根に分割し、2 つの小さい多項式を再帰します (再帰ごとに 2 倍の数値を評価できるようにします)。

これを視覚化するために、アルゴリズムを通る多項式のパスを示すツリーを作成しようとしています。どのように始めたらよいかよくわかりません。どなたか始めていただけませんか？完全なツリーが正しい道に進むための簡単な例であるとは思っていません。

特定のソートアルゴリズムを実装すると、Googleが助けたくないという問題に遭遇しました...最初にアルゴリズムに関するいくつかの言葉：

ライオンズシェアとは、入力 (配列) を 3 つの部分に分割することです: 2 つの重要な数字 (赤と青、赤 <= 青をアサート) を選択すると、分割の要素は (1) 両方よりも少なくなり、(2) のどこかになります。と (3) ピボットの両方より大きい。これはうまく機能する部分です！

配列のソートは再帰的に行う必要があります。パーティションを分割する前に任意のピボットを使用して入力を分割し、定義ごとにソートされた長さ 1 または 2 のパーティクルになります。というか、非常に簡単にソートできます。

問題は、1 つのキー値で構成される長さ >= 3 のパーティションです。再度パーティション化すると、選択されたピボットに関係なく、すべての要素が後で同じパーティションに配置され、最終的にスタック オーバーフローが発生します。だからこそ、これには解決策があると確信しているので、あなたが私を助けることができると思いました.

必須の JavaCode スニペット: パーティショニング - ドイツ語のデバッグで申し訳ありません。翻訳も面倒です。IntTuple は 2 つの整数しか保持できません。ばかげたことは何もありません。

必須の JavaCode スニペット: 並べ替え

アイデアをお寄せいただきありがとうございます。

よろしく、LDer

もっと：私はこのハッキーで厄介な解決策を思いついた：

より読みやすいバージョンの作成を手伝ってくれる人はいますか?

MORE : こちらの方がずっと良く見えます:

赤/青を明示的に渡していませんが、toto2 に感謝します。

MORE : toto2 が再び完全にポイントを持っているため、ランダム性が増します:

私はマージソートアルゴリズムを実装するプログラムを作成していますが、毎回2つの部分に分割するのではなく、毎回3つの部分に分割し、再帰的にマージソートします。基本的にはマージソートですが、2つの部分でマージソートするのではなく、毎回3でマージソートするので、かなり楽しいですね。まあ、それは間違いなくそうではありません。

これが私のマージソートの実装です：

マージ方法は次のとおりです。

マージメソッド内のコメントには、私が作成しようとした別のマージメソッドがありますが、それはまったくうまく終了せず、事態はさらに複雑になりましたが、参照用にそのままにしておきました。

問題は、これがまったく機能しないことです。たとえば、次のような場合です。

入力：6 5 4 3 2 1

それから私は持っているでしょう：

出力：[2、1、4、3、6、5]

私は正直にこれに一生懸命努力しました、そして2日間続けて、私はこの種のマージソートについて聞いているのは2人だけでした、そしてGoogleで何時間も検索した後、私はここで同様の質問（理解するには複雑すぎました）と別のスレッドを見つけました決して答えられなかったwikiの答えで。

もちろん、私は学ぼうとしているので直接的な解決策を求めているわけではありませんが、ヒントやヒント、そして私が間違ったことをしたことが大いに役立ちます。

前もって感謝します。

実行時間を O(n*logn) にするために、分割統治法を使用して次のアルゴリズムを実装しようとしています。

一連の数値 a_1、a_2、…、a_n および数値 k が与えられた場合、a_i + a_j を最大化しながら 1<= j – i <= k となるような i と j を見つけます。

たとえば、シーケンス 10,2,0,8,1,7,1,0,11 および k = 2 の場合、最大値は 15 = 8 + 7 です。

ある種の分割統治法を実装しましたが、各分割間隔を横切る値をチェックする方法を理解するのに苦労しています。これが私がこれまでに持っているものです：

O(n^ 2) 複雑さ。

これをどのように継続できるかについての指針やヒントがあれば、それは大歓迎です. また、私は現在、配列に偶数個の整数があるという仮定の下で作業しています。みんなありがとう。

「アルゴリズムの紹介」で説明されているアルゴリズムを使用して Mergesort を実装しています。ただし、実行するたびに、ソートされた配列の最初の要素としてガベージ値を取得します。そのコードは次のとおりです。

私はバイナリ検索の分割統治バージョンを作成しようとしていますが、配列を2つのサブ配列に分割し、マージソートでのマージに似た検索を行うものです。これは、cilkで使用したいためです。私はそれをそのようにしなければなりません。これは私が書いたコードです。有効なキー値に -1 を返すので、何か問題があるようです。

分割統治アルゴリズムがブルートフォースよりも速く実行されることが多いのはなぜですか？たとえば、最も近いポイントのペアを検索します。私はあなたが私に数学的証明を見せてくれることを知っています。しかし、直感的に、なぜこれが起こるのですか？魔法？

理論的には、「分割統治はブルートフォースよりも常に優れている」というのは本当ですか？そうでない場合、反例はありますか？

ある数値の n 乗根を取得する方法について助けが必要です。

ユーザーは、番号 n と、ルートにしたい番号を入力します。cmath lib を使用せずに、分割統治法を使用してこれを解決する必要があります。

まだ動作しない私のコードは次のとおりです。

この問題にアプローチする方法についてのアイデアは、役に立ちます。

私はアルゴリズムに関するCourseraのコースをたどり、最も近いペアの問題の分割/征服アルゴリズムについて考えを思いつきました。それを明確にしたいと思います。

ラフガーデン教授のアルゴリズム (興味がある場合はここで確認できます) に従って: 与えられた点 P のセットに対して、2 つのコピー (X 方向と Y 方向に並べ替えられたもの) - Px と Py がある場合、アルゴリズムは次のように与えられます。

最も近いペア (Px、Py):

1. ポイントを左半分 - Q と右半分 - R に分割し、x 方向と y 方向に沿って両方の半分のソートされたコピーを形成します - Qx、Qy、Rx、Ry
2. closestPair(Qx,Qy) を点 p1 と q1 とする
3. closestPair(Rx,Ry) を p2,q2 とする
4. デルタを dist(p1,q1) と dist(p2,q2) の最小値とする
5. これは残念なケースです。p3,q3 を最も近い SplitPair(Px,Py,delta) とします。
6. 最良の結果を返す

さて、私が望む明確化はステップ 5 に関連しています。私が提案していることはほとんど改善されていないことを前もって言っておく必要がありますが、それでも興味がある場合は、先に読んでください。

R 教授は、ポイントは既に X 方向と Y 方向に並べ替えられているため、ステップ 5 で最適なペアを見つけるには、幅 2*delta のストリップ内のポイントを下から上に、内側で繰り返す必要があると述べています。ループ 7 回の比較のみが必要です。これを1つだけに改善できますか？

私がどのように可能であると考えているかをプレーン テキストで説明するのは少し難しいように思えたので、図を描いて紙に書き、ここにアップロードしました。

誰も思いつかなかったので、私の考えには間違いがあると確信しています。しかし、私は文字通りこれについて何時間も考えていたので、これを投稿する必要がありました. それは私の頭の中にあるすべてです。

誰かが私が間違っているところを指摘できますか?

再帰的線形検索の複雑さを分析したかった (分割統治法を使用)。log(n) ですか、それとも n ですか? log(n) でない場合、実際の複雑さとは何ですか?