1

時間の経過に伴う値を表す次の一連の数値があるとしましょう

1 2 3 10 1 20 40 60

現在、ある時点から別の時点までの最大の増加率を見つけるアルゴリズムを探しています。上記の場合、答えはペア (1, 60) で、6000% 増加します。

これまでのところ、私が考えることができる最良のアルゴリズムは総当たり法です。一連の反復を使用して、すべての可能なペアを検討します。

1 回目の反復:

1-2 1-3 1-10 .. 1-60

2回目の反復

 2-3 2-10 2-1 ... 2-60

（等。）

これは複雑さ O(n 3 ) を持っています。

また、別のアプローチも考えています。厳密に増加するシーケンスをすべて見つけて、それらの厳密に増加するシーケンスの増加率のみを決定します。

他に思い当たるアイデアはありますか？私の考えが間違っている場合は、私を修正してください!

4

4 に答える 4

2

私は問題を誤解したかもしれませんが、重要なのは2つの数字であるため、必要なのは最大数と最小数だけのようです。

while true:
    indexOfMax = max(list)
    indexOfMin = min(list)
    list.remove(indexOfMax)
    list.remove(indexOfMin)
    if(indexOfmax < indexOfMin)
        contine
    else if(indexOfMax == indexOfMin)
        return -1
    else
        SUCCESS
于 2011-02-05T01:23:41.043 に答える
0

私があなたの問題を正しく理解しているなら、あなたは配列の中で最も高い比率A [j] / A[i]を持つi<jの2つのインデックス（i、j）を探しています。もしそうなら、あなたはそれをこの関連する問題に還元することができます、それはあなたにA [j]-A [i]ができるだけ大きくなるようにi≤jでインデックス（i、j）を見つけるように頼みます。この問題には、この問題にも適応できる非常に高速なO（n）時間、O（1）空間アルゴリズムがあります。直感は、配列の最初の要素だけで構成される配列の問題を解決し、次に最初の2つの要素、次に最初の3つの要素などを解決することです。配列の最初のn個の要素の問題を解決したら、問題に対する全体的な解決策があります。

これを行う方法を考えてみましょう。最初に、配列の最初の要素だけを検討する場合、要素をそれ自体と比較することで得られる最良の増加率は0％です。ここで、最初のk個の配列要素の問題を（帰納的に）解決し、次の配列要素を見たときに何が起こるかを確認したいとします。これが発生すると、2つの条件のいずれかが成立します。まず、最初のk要素に対する最大パーセンテージの増加は、最初の（k + 1）要素に対する最大パーセンテージの増加でもある可能性があります。たとえば、（k + 1）番目の配列要素が非常に小さい場合、最初のk要素の何かからその値まで大幅なパーセンテージの増加を得ることができない可能性があります。次に、最大パーセンテージの増加は、最初のk個の要素の1つから（k + 1）番目の要素までである可能性があります。

これらの2つのケースを組み合わせると、最初のk+1要素に対する最良の増加率は最大値であることがわかります。

  • 最初のk個の要素の最大増加率、または
  • 最初のk個の要素の最小値から（k + 1）番目の要素へのパーセンテージの増加。

これを実装するには、これまでに見た最小値とパーセント増加を最大化するペアの2つの値を追跡しながら配列要素全体を反復処理します。例として、元の例の配列の場合

1  2  3  10  1  20  40  60

アルゴリズムは次のように機能します。

       1       2       3       10        1       20       40        60
min        1       1        1       1       1         1        1        1
best     (1,1)   (1, 2)  (1, 3)  (1, 10)  (1, 10)  (1, 20)   (1, 40)  (1, 60)

そして、最も高いパーセンテージの増加として（1、60）を出力します。このような別のアレイでは、次のようになります。

3   1   4   2   5

その場合、アルゴリズムは次のようにトレースします。3 1 4 2 5 min 3 1 1 1 1 best（3,3）（3,3）（1,4）（1,4）（1,5）

（1、5）を出力します。

このアルゴリズム全体はO（1）空間のみを使用し、O（n）時間で実行されます。これは、この問題に対する非常に優れたソリューションです。

または、配列内のすべての値の対数をとることで、この問題を直接最大の単一販売利益の問題に減らすことを考えることができます。その場合、log A [j] --log A [i]が最大化される値のペアを見つけた場合、これは（logarithmsのプロパティを使用して）log（A [j] / A [i]）が最大化されます。対数関数は単調に増加しているため、これは、意図したとおりにA [j] /A[i]が最大化される値のペアが見つかったことを意味します。

于 2011-08-30T20:06:02.340 に答える
0

私が理解しているように（あなたはあなたのコメントで私を訂正しませんでした）、あなたa[i]/a[j]はすべてのために最大化したいですj <= i。それが正しければ、それぞれiについて、その前の最小値を知る必要があるだけです。

int current_min = INFINITY;
double max_increase = 0;
for (int i = 0; i < n; ++i) {
    current_min = min(current_min, a[i]);
    max_increase = max(max_increase, a[i] / min);
}
于 2011-02-05T01:23:36.690 に答える
0

それでは、各数値をペアごとに比較して、2 番目の数値と最初の数値の比率が最も高いペアを確認したいだけでしょうか。2 つのループ (i=0 から n までのループと、j=i+1 から n までの内側のループ) を繰り返すだけで、O(n^2) が得られます。これは実際にはあなたの元のソリューションだと思いますが、複雑さは O(n^3) であると誤って言いました。n^2 です。

ただし、O(n log n) に到達する可能性があります。リストを取得して、各要素が (インデックス、値) のペアであるリストにします。次に、ペアの 2 番目の要素で並べ替えます。次に、リストに 2 つのポインターを持ちます。1 つは左から (0 から n-1)、もう 1 つは右から (n-1 から 0) です。左の要素の元のインデックスが右の要素の元のインデックスよりも小さい要素の最初のペアを見つけます。終わり。

1 2 3 10 1 20 40 60
becomes
(1,0) (2,1) (3,2) (10,3) (1, 4) (20, 5) (40, 6) (60,7)
becomes
(1,0) (1,4) (2,1) (3,2) (10,3) (20,5) (40,6) (60,7)

したがって、答えはインデックス 0 からインデックス 7 までの 60/1 です。

これがあなたが探しているものでない場合は、あなたの例の数字に対する正しい答えが何であるかを教えていただけると助かります.

于 2011-02-06T01:09:29.150 に答える