配列は、その要素の値が 0 番目のインデックスから ( k -1) インデックスまで増加するように与えられます。kで値は最小になり、n番目の要素を通じて再び増加し始めます。最小要素を見つけます。
基本的に、ソートされた 1 つのリストが別のリストに追加されます。例: (1, 2, 3, 4, 0 , 1, 2, 3)。
私は最小ヒープの構築、クイック選択、単純なトラバースなど、あらゆる種類のアルゴリズムを試しました。しかし、O(n)以下にはなりません。しかし、この配列にはパターンがあり、バイナリ検索のようなものが可能であることを示唆し、複雑さは O(log n) のようなものである必要がありますが、何も見つかりません。考え??
ありがとう
いいえドロップはどこにでもあり得ます、これに構造はありません。
極端なことを考えてください
1234567890
9012345678
1234056789
1357024689
それは最小の要素を見つけることになります。
バイナリ分割で1要素のオーバーラップを使用して、減少する範囲の幅方向のバイナリ検索を実行します。つまり、たとえば17個の要素がある場合は、要素を比較します
0,8
8,16
0,4
4,8
8,12
12,16
0,2
2,4
など、左側の要素が右側よりも大きい場合を探します。
そのような範囲を見つけたら、その範囲内で同じバイナリ検索を実行して、繰り返します。減少する隣接するペアが見つかるまで繰り返します。
平均的な複雑さはO（log n）以上で、最悪の場合はO（n）です。誰かがより厳密な平均複雑度の見積もりを得ることができますか？O（log n）とO（n）のほぼ「中間」のように見えますが、評価方法がわかりません。また、値の範囲と、あるメンバーから次のメンバーへの増分のサイズに関する追加の制約にも依存します。
要素間の増分が常に1の場合、O（log n）ソリューションがあります。
O（n）未満では実行できません。
この種の最悪のケースは常に私たちを悩ませ続けるでしょう-
増加するリストa1、a2、a3 .... ak、ak + 1 ...
たった1つの偏差でak<ak-1例：1,2,3,4,5,6,4,7,8,9,10
そして、他のすべての数値は、「k」または「ak」の値に関する情報をまったく保持しません。
最も簡単な解決策は、次の値が現在の値よりも小さくなるまでリストを順方向に調べるか、逆方向に現在の値よりも大きい値を見つけることです。それがO(n)です。
両方を同時に実行しても O(n) になりますが、実行時間はおそらく速くなります (複雑なプロセッサ/キャッシュ要因によって異なります)。
多くの分割統治型検索アルゴリズムはソートされたデータセットに依存しているため、アルゴリズム的に O(n) よりもはるかに高速に取得できるとは思いません。