algorithm - 同じアルゴリズムの異なる上限と下限

Question

それで、アルゴリズムの漸近境界について学び始めたところです
。質問: アルゴリズムで異なる下限と上限が見つかった場合、関数のシータについて何が言えますか?? （オメガ（n）とO（n ^ 2）と言います）。むしろ、そのようなアルゴリズムのタイトさについて何が言えるでしょうか?

私が読んだ本によると、シータは関数の同じ上限と下限のためのものです。この場合はどうですか？

Answer 1

その場合は何とも言えないと思います。

の定義Θ(f(n))は次のとおりです。

関数は、それがであり、かつであるΘ(f(n))場合にのみです。Ω(f(n))O(f(n))

nと の間で振動するなど、これらの動作を示す一部の病理学的機能については、n^2定義されません。

例：

f(x) = n if n is odd
       n^2 if n is even

あなたの境界はこれにきつくなりますがΩ(n)、どの関数にも定義されていません。O(n^2)Θ(f(n))

参照: Θ(n) と O(n) の違いは何ですか?

Answer 2

ちょっとした実用性のΘ(f(n))ために、どのアルゴリズムにも当てはまらないアルゴリズムの 1 つf(n)に挿入ソートがあります。Ω(n)すでにソートされているリストの場合、すべてのステップで挿入に必要な操作は1つだけなので、実行されO(n^2)ますが、一般的な場合に実行されます。振動する関数や非連続的な関数の構築は、通常、教訓的な目的で行われますが、私の経験では、そのような関数が実際のアルゴリズムで表示されることはめったにありません。

タイトネスに関しては、アルゴリズムに対して提案されている上限と下限を参照して、このコンテキストでのみ聞いたことがあります。再び挿入ソートの例に関して言えば、与えられた境界は、そのサイズ (下限) に比例して時間内に実際に実行できる問題のインスタンスと、実行されない問題の他のインスタンスがあるという意味でタイトです。サイズが 2 次より小さい時間。有効であるが、挿入並べ替えには厳密でΩ(1)はない境界は、任意のサイズのリストを一定時間で並べ替えることができず、要素O(n^3)のリストを常にn厳密なO(n^2)時間で並べ替えることができるためです。これは桁違いに小さいため、あなたは確かにそれを行うことができますO(n^3). 境界とは、アルゴリズムのパフォーマンスとして期待できるものについて大まかなアイデアを提供することです。これにより、ソリューションがどれほど効率的であるかを知ることができます。タイトな境界が最も望ましいのは、どちらも大雑把なアイデアを提供し、境界が許すすべての複雑さを実際に必要とする極端なケース (場合によっては一般的なケースでもある) があるという意味でそのアイデアが最適であるためです。

平均的なケースの複雑さには限界がありません。アルゴリズムが「ほとんどの場合」にどれほど効率的であるかを「のみ」説明します。たとえば、最高の場合の複雑さが、最悪の場合の複雑さが、平均的な場合の複雑さが であるクイック ソートを考えてみましょう。これは、ほとんどすべてのケースで、クイック ソートが一般的なソートと同じくらい高速であること (つまり、ケースの平均複雑度) を示しています。また、それよりも解決に時間がかかるクイックソートの問題のインスタンス (最悪の場合の複雑さ -> 上限)。Ω(n)O(n^2)O(n log n)