問題タブ [divide-and-conquer]

今、私は N 個の異なる整数を持っています。値が O(NlogN) 時間で間隔の終点の間にある数値が最も多い間隔を見つける必要があります。それは私の最終試験の「分割統治」カテゴリにあるので、私はそれを「分割統治」問題と呼んでいます。私はそれについて2週間考えていて、多くの実験を行ってきましたが、どれも正しくありません(ブルートフォースアルゴリズムと比較して)。誰かが私を助けることができますか？

例:

8,1,3,4,7. 答えは1～7です。

2,6,5,4,9,8. 答えは 2-9 または 2-8 です。

「間隔」という言葉は私の意味を表していないと思います。値がサブシーケンスのエンドポイントの間にある数値が最も多い配列のサブシーケンスを見つけることを意味します。例1: 「1,3,4,7」には2つの数字(3,4)があり、例2: 「2,6,5,4,9」と「2,6,5,4,9」の両方があります,8" には 3 つの数字 (6,5,4) があります。

これが私のコードです（O（n ^ 2））。@Vaughn Catoこれを使用して、コードと比較します。

免責事項: これは割り当て用です。私は明示的なコードを求めているのではなく、コードのエラーを修正できるように、関連するアルゴリズムを理解するのに十分な助けを求めているだけです。

さて、あなたはおそらく部分配列の最大化問題に精通しているでしょう: 配列内の連続する整数の最大ブロックを計算して返します。簡単ですが、この割り当てでは、O(n^3)、O(n^2)、O(n log n) という 3 つの異なる複雑さで実行する必要があります。最初の 2 つは問題なく取得できましたが (ブルート フォース)、3 番目は頭痛の種です..文字通り。

アルゴリズムがどのように機能するかを理解しています。配列は関数に渡され、再帰的に半分に分割され、個々のコンポーネントを比較して各半分の最大サブ配列を見つけます。次に、最大の部分配列は完全に左半分または右半分、または 2 つに重なるセグメントに存在する必要があるため、左右に重なる最大の部分配列を見つけなければなりません。各ケースの最大サブ配列を比較すると、最大のものが戻り値になります。

そのタスクを適切に実行するコードを書いたと思いますが、その評価は間違っているようです。インストラクターと TA に助けを求めて連絡を取ろうとしてきましたが、どちらともうまくいっているようには感じません。以下は、これまでになんとか書いたコードです。明らかなエラーがあれば教えてください。繰り返しますが、明示的なコードや回答を探しているわけではありませんが、何が間違っているのかを理解するのに役立ちます。ここで紹介した同様のケースをすべて調べましたが、本当に役立つものは見つかりませんでした。また、ガイダンスを求めて Google 検索を何度も行いましたが、それもあまり役に立ちません。とにかく、問題のコードは次のとおりです。

編集:私が得ているエラーは間違った結果です。他の 2 つのアルゴリズム間で一貫した正しい結果が得られましたが、これは正しくありません。

編集＃2：これは私のコードの更新版で、少しスリムになり、いくつか修正しました。まだ正しく動作していませんが、もっと近くなるはずです...

したがって、問題は、x が行ごとおよび列ごとに昇順で並べ替えられた行列の要素の 1 つに含まれているかどうかを調べることです。

例 ：

1 2 3

4 5 6

7 8 9

この問題の分割統治法による解決策の時間計算量を見つけることに興味があります。私はそれをグーグルで検索しましたが、O(m+n) ソリューションのみを見つけました。また、このSearch a sorted 2D matrixからも見つかりました。しかし、彼は「T（R）= 3T（R / 4）」と（回答のコメント）言っていますが、なぜf（R）= 0なのですか？

問題は、マスター定理を使用した分割統治法ソリューションの複雑さは何ですか? T(R) = 3T(R/4) + f(R) では、f(R) はどうあるべきですか?

それが役立つ場合、これは私の分割統治ソリューションです：

解決策を明確にするために編集：

アルゴリズム : 1. 行列の中央の要素を検索値と比較します 2. 値が m(i,j) と等しい場合は true を返します 3. 値が小さい場合、値の右上、左上、左下を検索します行列 4. 値が大きい場合は、行列の右上、右下、左下の値を検索します

今学期はアルゴリズムコースがあります。順序統計についての講義に到達するまでは、すべて問題ありません。

これがその講義の最初のスライドです：

次のことがわかりません。

注文統計とは何ですか？

n個の要素の中でi番目に小さいものとはどういう意味ですか？「i番目」とは何かを知るための例が必要です！

これらについて簡単な説明はありますか？

私が知っているのは、次のスライドがそれについてであるため、これは分割統治に関連しているということだけです:)。

私は自分で次のタスクを解決しました：

1 <= i<=nおよびA[i]=iとなるようなインデックスiを見つけるアルゴリズムを与えてください。そのようなインデックスが存在することを条件とします。そのようなインデックスがある場合、アルゴリズムはそれらのいずれかを返すことができます。

分割統治法を使用した結果、次のようになりました。

最初にそれが正しいかどうか尋ねたかったですか？はいと思います。

この場合の再帰T（n）は何ですか？

私は推測します：

2T（n / 2）+ O（1）---->そうですか？マスター定理を適用して漸化式を解決する方法を詳細に説明できますか？

a = 2 b = 2 f（n）= 1 n ^ logba = n ---> n vs 1なので、O（n）->????につながるケース1があります。右？

私たちはデータ構造のクラスで分割統治アルゴリズムを使い始めていますが、何をすべきかを完全に理解するのに苦労しています。以下は、基本的に配列を合計するプログラムを作成するように求めていますが、基数が 4 になるまで分割して征服する必要があります。チャンクを一緒に。どこから始めればよいかさえわかりません。少しだけ説明と理解が必要です。先生はあまり役に立ちませんでした。配列には、1000 未満の 2 のべき乗の数の行が含まれています。

問題 n 個の整数の配列を合計するための分割統治アルゴリズムを書きなさい。このアルゴリズムの基本ケースは、副問題のサイズが 4 以下の場合です。この場合、反復ループを使用して副問題の整数を合計します。次のことを行う必要があります。

これが私の分割統治プログラムですが、エラーが発生します。私は正しい方向に向かっていますか？

getSum.sumArray（getSum.java:16）のスレッド"main"java.lang.StackOverflowErrorのエラー例外は次のとおりです。

16の配列を取得し、それをベースケース4に分解する簡単な例を探しています。配列を吐き出し、再度分割する方法を完全に理解するのに問題があります。次に、最後にすべての分割を結合します。

私は分割統治アルゴリズムを学ぼうとしていて、Javaを使用して機能すると思ったものを思いついた。アルゴリズムは、2を底とするサイズnの配列を取ることになっています。配列を4の底の場合に分割してから、インデックスの配列を合計する必要があります。次に、それらすべてを合計して、配列全体の合計を求めます。これが私がこれまでにJavaで行ったことと私のエラーです。私は少なくとも分割統治アルゴリズムの正しい軌道に乗っていますか？

発生した例外：

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

私は有名なスカイラインの問題を解決しようとしています（gifを参照）：

入力

（1,11,5）、（2,6,7）、（3,13,9）、（12,7,16）、（14,3,25）、（19,18,22）、（23 、13,29）、（24,4,28）

戻る必要がある場合は、他の建物の背後にあるポイントがなくなり、Y軸の変化の座標が戻るスカイラインにある必要があります。

（1、11）、（3、13）、（9、0）、（12、7）、（16、3）、（19、18）、（22、3）、（23、13）、（29 、0）

O（n lg n）の実行時間を達成するために、アルゴリズムに分割統治アプローチを使用してこれを実行しようとしていますが、マージ部分で立ち往生しています。

それについて考えるたびに私は混乱します。たとえば、最初にスカイラインがどれであるかを確認します。たとえば、X座標が低い方を確認してから、その+その高さを新しいスカイラインに追加します。しかし、他の2つのスカイラインの背後にあるスカイラインに遭遇した場合、この「衝突」をどのように検出できますか？

最初に、left.x2 <right.x1かどうかをチェックして、スカイラインにオーバーラップがあるかどうかをチェックしますか？しかし、私は最初に何をチェックすべきだと思いますか？x軸の優先順位が重なると、すべてが大きな鶏卵の混乱に変わります。

多分私はあまりにも複雑だと思っていますか？必要なのは、すべての交差点での最高のy座標のセットですが、このようにアプローチする必要がありますか？

リスト内の文字列間のコサイン類似度を計算する必要があります。たとえば、1,000 万を超える文字列のリストがあり、各文字列は、リスト内の他のすべての文字列との類似性を判断する必要があります。そのようなタスクを効率的かつ迅速に行うために使用できる最適なアルゴリズムは何ですか? 分割統治アルゴリズムは適用できますか?

編集

特定の文字列に最も類似している文字列を特定し、類似性に関連付けられた測定値/スコアを取得できるようにしたいと考えています。私がやりたいことは、最初はクラスターの数がわからないクラスター化に沿っていると思います。