10

単調に増加してから単調に減少するシーケンスの最大値または最小値を見つけることは、O(log n) で行うことができます。

ただし、そのようなシーケンスに数値が存在するかどうかを確認したい場合、これはO(log n)でも実行できますか?

私はそれが可能だとは思わない。この例を考えてみましょう: 1 4 5 6 7 10 8 3 2 0.

この例では、シーケンスに「2」が含まれているかどうかを確認する必要がある場合、検索スペースを元の検索スペースの半分に分割する条件はありません。最悪の場合、2 を検索しようとすると、両方の半分を確認する必要があるため、O(n) になります。

この検索が O(log n) 時間で行われるかどうかを知りたいですか?

4

3 に答える 3

12

お気づきのように、O（logn）で最大値（およびその位置）を見つけることができます。次に、O（logn）でもある各部分でバイナリ検索を実行できます。

上記の例では、位置5で最大10を見つけます。次に、サブシーケンス[0..5]（1、4、5、6、7、10）で二分探索を実行します。2が見つからないため、他の部分（10、8、3、2、0）で二分探索を実行します。

O（logn）の最大値を見つけるには：中央の2つの要素を見てください：7 <10です。したがって、まだ増加している部分にあり、シーケンスの右半分で最大値を探す必要があります：（10、8 、3、2、0）。8と3を見て、左側の部分（10、8）に進みます。

于 2012-07-18T07:20:08.557 に答える