非単調な最悪ケースの複雑さの例

Question

誰かが単調でないワーストケースの動作を持つ自然なプログラムまたはアルゴリズムを認識していますか？

単調でないワーストケースの動作は、サイズn + 1の入力に対する最悪の場合の実行時間が、サイズnの入力の最悪の場合の実行時間よりも短いような自然数nであることを意味します。

もちろん、この動作でプログラムを構築するのは簡単です。これは、自然プログラムではnが小さい（n = 1のような）場合にも起こります。しかし、大きなnに対して単調でない有用なアルゴリズムに興味があります。

Answer 1

誰かが の単調でないワーストケースの動作を持つ自然なプログラムまたはアルゴリズムを認識していますか？

"自然なプログラムまたはアルゴリズム"を定義してください。概念「アルゴリズム」には、私が知っている定義があります。また、単調でない最悪の場合の実行時の複雑さを持つアルゴリズムもあります。それはそれが解決する問題のクラスのために必要な作業や実行時の複雑さが最小限である場合、プログラムは "自然"ですか？その場合、BubbleSortはアルゴリズムではないと主張しますか？さらに重要なのは、モノトーンではないワーストケースの動作を持つ最も効率的な解決策を定義できます。そのような問題は「不自然」であろうか？あなたは「自然の問題」の定義は何ですか？

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

本当の質問は何ですか？あなたが自然/有用なアルゴリズムと問題の定義にコミットするまで、あなたの質問には答えがありません。あなたは、現実世界で人々がすでに使用している既存のアルゴリズムにのみ興味がありますか？もしそうなら、あなたはそのことを述べなければならず、その問題は文献を捜す一つになります。率直に言って、私は非単調ランタイムの複雑さとアルゴリズムの多くの例を妨げる「自然、有用なアルゴリズム」...

の合理的な定義を想像することはできません。しかし、私は非である有用なアルゴリズムに興味モノラルfor 大きいn。

「有用なアルゴリズム」を定義してください。概念「アルゴリズム」には、私が知っている定義があります。また、単調でない最悪の場合の実行時の複雑さを持つアルゴリズムもあります。アルゴリズムが何らかの問題を正しく解決すれば、アルゴリズムは「有益」ですか？単調でないランタイムの複雑さを伴うアルゴリズムで解決できる問題を簡単に定義できます。

Answer 2

バイナリ検索について考えてみましょう。

バイナリ検索を実装するときは、分割する配列セグメントの長さが奇数であるケースについて考える必要があります。その時点で、2つの選択肢があります。 1.切り上げ/切り捨て 2.続行する前に両方のインデックスを確認して決定してください。

最初のケースを選択した場合（切り捨てを想定します）。探している番号が中点を通過した奇数長配列の場合は、余分な繰り返しを行います。
この奇妙な配列に1つ以上の要素が追加されていると、その余分な繰り返しが保存されます。

2番目の場合は、より奇数回のアルゴリズムを実行すると、余分な要素で使用された場合に比べてさらに多くの比較が必要になります。

これはすべて実装に依存しているため、実際のアルゴリズムがなくても実際の答えが得られないことになります。

また、これは実際の実行時差分と漸近差分ではないことを前提としています。そうでない場合、答えは「いいえ」になります。非単調ワーストケース漸近実行時間のアルゴリズムはありません。それは「最悪の場合」という概念に反します。