整数配列から、平均が最大にA[N]なる間隔を見つけたいと思います。[i,j](A[i] + A[i + 1] + .. + A[j]) / (j - i + 1)
間隔の長さは(j - i + 1)より長くする必要がありますL。(L >= 1)
i～jごとに平均をとろうと思ったのですが、このようにするには遅すぎます。(Nが大きすぎます)
よりも高速なアルゴリズムはありO(N^2)ますか? または、そのためのランダム化された方法が存在するかどうかを知りたいです。
質問する
1457 次
1 に答える
10
が配列の最大要素値に比例するO(N*logC)アルゴリズムがあります。C最近の論文のいくつかのより複雑なアルゴリズムと比較すると、このアルゴリズムは理解しやすく、短時間で実装でき、実用上十分に高速です。
簡単にするために、配列には負でない整数が少なくとも 1 つあると仮定します。
アルゴリズムは二分探索に基づいています。最初に、最終的な答えが の範囲内になければならないことがわかり、[0, max(A)]十分に小さくなるまで (たとえば10 -6 )、各反復でこの間隔を半分にします。各反復で、利用可能な間隔が であると仮定すると[a,b]、最大平均が より小さくないかどうかを確認する必要があり(a+b)/2ます。もしそうなら、より小さな間隔を取得する[(a+b)/2, b]か、そうでなければ取得し[a, (a+b)/2]ます。
問題は次のとおりです。数値が与えられたK場合、最終的な答えが少なくとも であることを確認するにはどうすればよいKですか?
平均が少なくともKであるiと仮定jし(A[i] + A[i+1] + ... + A[j]) / (j - i + 1) >= Kます。両辺に を掛け(j-i+1)、右辺を左に移動すると、 が得られ(A[i] - K) + (A[i+1] - K) + ... + (A[j] - K) >= 0ます。
では、 となる間隔( )B[i] = A[i] - Kを見つけるだけで済みます。ここでの問題は次のとおりです: arrayと lengthが与えられた場合、長さが より大きい最大合計の間隔を見つける必要があります。最大合計が の場合、元の平均数が可能です。[i, j]j - i + 1 > LB[i] + ... + B[j] >= 0BLL>= 0K
2 番目の問題は、リニア スキャンによって解決できます。sumB[0] = 0、 としましょうsumB[i] = B[1] + B[2] + ... + B[i]。各インデックスについてi、 で終了した最大合計間隔B[i]は ですsumB[i] - min(sumB[0], sumB[1], ..., sumB[i-L-1])。を増やしながら配列をスキャンすると、その場iで を維持できmin(sumB[0], ..., sumB[i-L-1])ます。
サブ問題の時間計算量は ですO(N)。そしてO(logC)反復が必要なので、合計の複雑さはO(N*logC)です。
Ps この種の「平均問題」は、分数計画法 と呼ばれる問題のファミリーに属します。同様の問題は、最小平均加重スパニング ツリー、最小平均加重サイクルなどです。
追伸。はO(logC)ルーズ バウンドです。慎重な分析によってそれを減らすことができると思います。
于 2012-08-26T13:08:19.077 に答える