runtime - 単調ではない最悪の場合の複雑さの例

Question

単調ではない最悪のケースの動作をする自然なプログラムまたはアルゴリズムを知っている人はいますか?

単調ではない最悪の場合の動作とは、サイズ n+1 の入力の最悪の場合の実行時間が、サイズ n の入力の場合の最悪の場合の実行よりも短くなる自然数 n が存在することを意味します。

もちろん、この振る舞いでプログラムを構築するのは簡単です。これは、自然なプログラムの小さな n (n = 1 など) で発生する場合もあります。しかし、大きな n に対して単調ではない便利なアルゴリズムに興味があります。

Answer 1

二分探索について考えてみましょう。

二分探索を実装する場合、分割する配列セグメントの長さが奇数の場合について考える必要があります。その時点で 2 つの選択肢があります。

最初のケースを選択した場合 (切り捨てと仮定します)。検索している数が中間点を通過した数である奇数長の配列の場合、追加の反復を行う必要があります。
その奇数の配列にもう 1 つの要素が追加されていれば、余分な反復を節約できたはずです。

2 番目のケースを選択した場合、アルゴリズムのほとんどの実行では、奇数回の繰り返しを使用した場合でも、余分な要素を使用した場合よりも多くの比較が必要になります。

これはすべて実装に大きく依存するため、実際のアルゴリズム (さらには実際の実装) がなければ本当の答えは得られないことに注意してください。

また、これはすべて、漸近的な差分ではなく、実際の実行時の差分について話しているという仮定に基づいています。そうでない場合、答えは「いいえ」になります。非単調な最悪の場合の漸近的な実行時間を持つアルゴリズムはありません。それは「最悪の場合」の概念に反するでしょう。

Answer 2

単調ではない最悪のケースの動作をする自然なプログラムまたはアルゴリズムを知っている人はいますか?

「自然プログラムまたはアルゴリズム」を定義してください。「アルゴリズム」という概念には私が知っている定義があり、単調ではない最悪の場合のランタイムの複雑さを持つアルゴリズムが確かに存在します (あなたが正しく認めているように)。不必要な作業を行わない場合、または解決する問題のクラスに対して実行時の複雑さが最小限である場合、プログラムは「自然」ですか? その場合、BubbleSort はアルゴリズムではないと主張しますか? さらに重要なことは、問題を、単調ではない最悪のケースの動作を持つ最も効率的なソリューションと定義できることです。そのような問題は「不自然」でしょうか？「自然な問題」の定義は何ですか?

もちろん、この振る舞いでプログラムを構築するのは簡単です。

それでは、本当の質問は何ですか？自然で有用なアルゴリズムと問題の定義にコミットするまで、あなたの質問には答えがありません。人々が現実の世界ですでに使用している既存のアルゴリズムだけに興味がありますか? もしそうなら、あなたはそれを述べるべきであり、問​​題は文献を検索することの1つになります. 率直に言って、単調ではないランタイムの複雑さを持つアルゴリズムの多くの例を排除する「自然で有用なアルゴリズム」の合理的な定義を想像することはできません...

しかし、大きな n に対して単調ではない便利なアルゴリズムに興味があります。

「有用なアルゴリズム」を定義してください。「アルゴリズム」という概念には私が知っている定義があり、単調ではない最悪の場合のランタイムの複雑さを持つアルゴリズムが確かに存在します (あなたが正しく認めているように)。問題を正しく解決する場合、アルゴリズムは「有用」ですか? 単調ではないランタイムの複雑さを持つアルゴリズムによって解決できる問題を簡単に定義できます。