問題タブ [divide-and-conquer]

(n log n) を示すアルゴリズムを使用して、最大サブ配列問題を実装したいと考えています。

最大連続サブ配列、または配列内の連続要素の最大合計を見つけます。

仮定:すべての要素が負の数ではない

私はいくぶん実用的な解決策を持っています。問題は、重なっている中央の配列と、重なっているサブの問題を指定する適切なインデックスにあり、一部の配列は他の配列で正しい答えを得ていません。

比較と正確さの確認のために、Kadane のアルゴリズムとして知られるソリューションを実装しました (複雑さは Omega(n) だと思います)。

これはKandaneのアルゴリズムです(http://en.wikipedia.org/wiki/Maximum_subarray_problem):

分割と征服を使用してサブ配列の最大値を比較し、再帰が終了するまで、最大値を持つサブ配列で再帰呼び出しを行う私の再帰的実装

結果: 配列 subArrayProblem1 を使用 = {1, 2, 3, 4, 5, 6, 7, 8};

Kadane(int array []): 36 low: 0 mid: 4 1,2,3,4,5,6,7,8,mid: 4 high: 7 lowCenter: 6 highCenter: 6

findMaxSubArray(int[] array, int lowIndex, int highIndex) global Max Range, low:7 high: 7 global Max Sum:36 BUILD SUCCESSFUL (合計時間: 0 秒)

Kadane と比較するとグローバルな最大合計は正確ですが、低インデックスと高インデックスの範囲は最後の再帰呼び出しを反映しています。

結果: 配列 subArrayProblem を使用 = {100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97};

Kadane(int array []): 1607 low: 0 mid: 8 100,113,110,85,105,102,86,63,mid+1: 9 high: 16 101,94,106,101,79,94,90,97,lowCenter: 16 highCenter: 15

findMaxSubArray(int[] array, int lowIndex, int highIndex) グローバル最大範囲、低:16 高: 16 グローバル最大合計:1526

グローバル最大値が正しくありません。違いは実際には 1 要素であり、要素 81 であることに注意してください

線形 (n log n) 時間と対数 (log n) 余分なスペースでリンク リストをランダムにシャッフルする分割統治アルゴリズムを使用して、リンク リストをシャッフルしようとしています。

値の単純な配列で使用できるのと同様のクヌース シャッフルを実行できることは認識していますが、分割統治法でこれを行う方法がわかりません。私が言いたいのは、実際に何を分割しているのかということです。リスト内の個々のノードに分割してから、ランダムな値を使用してリストをランダムに組み立て直しますか?

または、各ノードに乱数を与えてから、乱数に基づいてノードでマージソートを実行しますか?

まず、問題があると言います。10億桁の円周率を計算するか、多数の階乗を計算するか、大きなリストに対してマージソートを実行します。問題をより小さなタスクに分割し、各タスクを同時に実行して、結果を結合したいと思います。まず、このタイプの並行性の名前は何ですか？Clojureでどのように実行しますか？

アイデアは、最初の k/2 リストと 2 番目の k/2 リストを再帰的にマージし、次にマージされた 2 つのリストを 1 つのリストにマージして返すことです。

最初の k/2 を 2 番目の k/2 リストと再帰的にマージすることが何を意味するのか混乱しています。誰かがこれを明確にしたり、この再帰を説明する疑似コードを調べたりできますか?

誰かがnビット文字列（すべての可能な組み合わせ）を生成する方法を教えてもらえますか？つまり、分割統治法を使用して0から2^n-1までのビットを数えます。

次のアルゴリズムでこれを行うことができましたが、空間の複雑さと時間の複雑さはO（2 ^ n）です。誰かが私に（分割統治法を使用して）これよりも少ないスペースを必要とするより良いアルゴリズムを教えてもらえますか？

プログラムの要点は、ブルートフォース法（機能している！）と分割統治法（機能していない）の両方を使用して、株価が変動する1次元配列の最大サブ配列を見つけることです。プログラムの目的は、一連の日数（したがって、構造体のlsubとrsub）とそれらの日の最大利益を見つけることです。

このパワーポイントのように私がオンラインで見たところはどこでも、私のコードが機能するはずであることを示しています。私もこれに似たものを見ましたが、StackOverflowのJavaでは、そのコードの実装も機能しません。これがそのJavaプログラムへのリンクです。

私のコードは次のとおりです。

サンプルデータセット:(それらは別々の行にあるはずですが、それは私にそうさせません。）

意図した出力は次のとおりです。

最大値は次のとおりです：43

左の添え字は次のとおりです：8

右の添え字は次のとおりです。11

順列問題の検索ツリーを生成したいと思います。私の要件は次のとおりです。そのために分割統治戦略を使用したい

木の長さ3の順列の例を示しています。

マージソートはかなり一般的なソート アルゴリズムであり、実際に動作するマージソート アルゴリズムを作成しました。それから私はそれを最適化したい。最初のステップは、それを再帰から反復に変換することでした。次に、他に最適化できるものを識別できませんでした。インターネット上の多くの記事を調べた後、multi-merge sort とtiled merge-sortを使用する 2 つのメカニズムを取得しました。しかし、どのドキュメントも疑似コードを提供しておらず、それを行う方法について多くを説明する気さえありませんでした.キャッシュフレンドリーでローカリティヒットの改善など、著者が言う利点をどのように提供するか.

誰でもこの問題について詳しく説明できますか?可能であれば、疑似コードを提供できますか? 具体的には、キャッシュフレンドリーにする方法を知りたいです。これらが何であるかはまったくわかりません。そうでなければ、自分で試してみたでしょう。

分割統治法のようなソートアルゴリズムについては、1つの要素だけが残るまで繰り返すのではなく、特定のしきい値、たとえば30要素に達したときにシフトする方がよいことをMerge-Sortどこでも読んでいます。それは問題ありませんが、なぜだけですか？なぜそうではないのですか、どちらも同様のパフォーマンスを持っていますか？多くの要素が事前に並べ替えられている場合にのみ便利ですが（ただし、その利点もあるはずです）、それ以外の場合は、他の2つよりも効率的である必要があります。QuicksortInsertion-SortInsertion-SortBubble-SortSelection-SortO(N^2)Insertion-SortBubble-Sort

そして第二に、このリンクでは、2番目の回答とそれに付随するコメントで、特定のまでO(N log N)と比較してパフォーマンスが低いと述べています。どうして？すべてのN>=2であるため、常にパフォーマンスが低下するはずです。O(N^2)NN^2N log NN > log N

助言？

並べ替えられていない配列と要素の数が与えられた場合、各要素について、数値-1がない場合は、それ自体と配列内で彼よりも小さい最も遠い要素との間の要素の数を出力する必要があります。

例：

入力：10 6 10 3 9 15出力：3 1 1 -1 -1 -1

私はすでにそれをしました、しかし私の教授はそれがはるかに効率的にすることができると言いました、もちろん私は実際にo（n ^ 2）をしています。分割統治？、二分探索？

私の解決策：