array[n]整数の大きな配列が入力として与えられます。2 つのインデックス値が与えられます - start,end。非常に迅速に検索することが望まれます- min & max in the set [start,end](包括的) およびmax in the rest of array([開始、終了] を除く)。
例えば-
配列 - 3 4 2 2 1 3 12 5 7 9 7 10 1 5 2 3 1 1
開始、終了 - 2,7
[2,7] の最小、最大 -- 1,12
残りの最大 - 10
線形よりも優れたものは考えられません。しかし、これは十分ではなくn is of order 10^5、そのような検索操作の数も同じ順序です。
どんな助けでも大歓迎です。
あなたの質問を理解する方法は、固定配列で前処理を行い、最大検索操作を非常に高速にすることです。
この回答は、O(nlogn) 前処理作業を行い、その後に各クエリに対して O(1) 作業を行うアプローチについて説明しています。
アイデアは、2 つの 2 次元配列 BIG[a,k] と SMALL[a,k] を準備することです。
1. BIG[a,k] is the max of the 2^k elements starting at a
2. SMALL[a,k] is the min of the 2^k elements starting at a
この配列を再帰的に計算するには、k==0 から開始し、前の 2 つの要素を組み合わせて上位の各要素の値を作成します。
BIG[a,k] = max(BIG[a,k-1] , BIG[a+2^(k-1),k-1])
SMALL[a,k] = min(SMALL[a,k-1] , SMALL[a+2^(k-1),k-1])
次に、事前に準備された 2 つの回答を組み合わせることで、任意の範囲の最大値と最小値を即座に見つけることができます。
100 から 133 までの要素の最大値を見つけたいとします。100 から 131 までの 32 要素の最大値 (BIG[100,5]) と、102 から 133 までの 32 要素の最大値 (BIG[102 内) は既にわかっています。 ,5]) したがって、これらの最大のものを見つけて答えを得ることができます。
同じロジックが最小値にも適用されます。2 つの重複する準備済みの回答をいつでも見つけることができ、それらを組み合わせて必要な回答を得ることができます。
線形は実行できる最善の方法であり、それを証明するのは比較的簡単です。
無限の瞬間的なメモリストレージとコストのないアクセスを想定して、それらを無視できるようにします.
さらに、部分文字列の最小値/最大値を見つけるというあなたのタスクを取り上げます。どちらも本質的にはまったく同じ機械的問題であると考えます。1 つは魔法のように比較で他の数値よりも小さい数値を追跡し、もう 1 つは比較よりも大きい数値を魔法のように追跡します。このアクションはコストがかからないと想定されます。
次に、サブアレイの問題の最小/最大を仮定しましょう。これは、任意の配列の最小/最大とまったく同じ問題であるためです。魔法のように、それが解決されたと仮定し、より大きな配列の最大。これを行うには、配列全体で最大の数が、実際には魔法のまぐれによって最初に見られる数であり、サブ配列で最大の数でもあり、サブ配列で最小の数でもあると仮定します。サブアレイですが、たまたま私たちがどれほど幸運であるかを知りません。どうすればわかりますか？
私たちがしなければならない最小の作業は、それと配列内の他のすべての数値を比較して、それが最大/最小であることを証明することです。これは、コストがあると想定している唯一のアクションです。
何回比較すればいいですか？N を配列の長さとし、任意の長さ N に対する操作の総数は N - 1 とします。配列に要素を追加すると、比較の数は、たとえすべてが広くても、同じ割合でスケーリングされます。とんでもない仮定が真実でした。
したがって、N が配列の長さであり、非常に非現実的な最良のシナリオでの可能な限り最良の操作の増加するコストの決定要因であるという点に到達しました。
最良のシナリオでは、操作は N でスケーリングされます。ごめんなさい。
/入力の並べ替えは、この最小限の操作よりも高価でなければならないため、操作を複数回実行していて、実際の結果を保存する方法がなかった場合にのみ適用されます。正確に負担がかかるわけではありません。
//マルチスレッドなどもすべてうまくいっています。そのためのコストを想定して、N をスレッド数で割ります。ただし、可能な限り最良のアルゴリズムでも線形にスケーリングします。
///データに関することを想定せずに線形よりも優れたスケーリングを行うには、実際には特に興味深い現象である必要があると思います...stackoverflowers?