2

指数時間である Θ(2^n) の実行時間を持つ再帰関係を解決しました。同じ再帰関係の Ω と O を見つける方法を教えてください。

Θ(2^n) なら O(2^n) でもいいのかな？下限である Ω を見つけるにはどうすればよいですか?

再帰関係を解いてみました：

T(n) = 2T(n-1) + C.

4

2 に答える 2

5

関数が Θ(f(n)) の場合、それは O(f(n)) と Ω(f(n)) の両方であることを意味します。

逆も成り立ち、関数が O(f(n)) と Ω(f(n)) の両方である場合、それは Θ(f(n)) です。

これの証明は簡単です:

g(n)=Θ(f(n)) => exists n0, c1 and c2 such that: c1f(n)<g(n)<c2f(n) for n>n0

前半のみを取り上げます。

exists n0 and c1 such that: c1f(n)<g(n) for n>n0 => g(n)=Ω(f(n))

そして後半：

exists n0 and c2 such that: g(n)<c2f(n) for n>n0 => g(n)=O(f(n))

逆の証明も同様です。

編集： Θ、O、およびΩの意味について少し説明します。

すでに Θ、O、および Ω の定義を見たことがあるはずです (そうでない場合は、上記の証明で 3 つすべてについて言及しました)。

では、それらの数学的定義以外に、それらは何を意味するのでしょうか?

基本的には、次のように考えてください。

  • g(n) = O(f(n))これは、nが大きくなると、f(n)常に よりも大きな値を持つことを意味しますg(n)。より正確に言えば、f(n)それ自体ではなく、その一定の倍数です。たとえば、n+100はO(n^2)です。また、 については、. これらすべての表記法があることは、関数がどのように成長するかを決定するのは定数であるため、定数は重要な役割を果たさないということです。O表記は関数の上限を示しているため、一意ではないことに注意してください。たとえば、 の場合、それはまた、などですが、（おそらく）そうではありませんn>101*n^2>n+100n>311*n^2>n+100f(n)f(n)=O(n)O(n^2)O(nlogn)O(sqrt(n))

  • g(n) = Ω(f(n))これはまさに O の逆数です。したがって、これはf(n)の下限でありg(n)(これも定数を掛けたものです)、これも一意ではないことを示しています。たとえば、 if f(n)=Ω(n)、 then もΩ(1)andΩ(1/n)です。あなたはいつも持っています

    g(n) = Ω(f(n)) <=> f(n) = O(g(n))

  • g(n) = Θ((f(n))これは、関数の成長に対する厳しい制限です。ほどスムーズではないかもしれませんが、基本的にはg(n)と同じ成長を意味します。これは、Θ が行うことの美しさと同様に滑らかではありません。単純に表現されていない実行時間のアルゴリズムがありますが、Θ を使用するとそれを分析できます。この写真のようなものです：f(n)f(n)f(n)g(n) = Θ((f(n))

    |                     ---- 2*f(n)
|                    /    /\  ---(g(n)
|                ----    /  \/    -------- f(n)
|               /       /        /
|           ----   /\  / --------
|          /  -----  \/ /
|      ----  /  --------
|     /     /  /
| ---- --------
|/    /
+---------------------------------------------

おもしろ情報：

  • f(n) = O(f(n))for all があるためn( 2*f(n)>f(n)2 は例であり、1 より大きい定数はどれでも良い)。関数の最小上限は、関数そのものです!
  • 同様に、f(n) = Ω(f(n))およびf(n) = Θ(f(n)). また、関数の最大の下限は関数自体です。
  • Θ は関数の正確な成長を示しており、アルゴリズムでそれを見つけた場合、それが最適な説明です。ただし、多くのアルゴリズムは複雑な動作をしたり、最良の場合でも入力に基づいて異なる成長を示します (たとえば、挿入ソートにはΘ(n)ソートされた入力がΘ(n^2)与えられ、逆にソートされた入力が与えられます)。したがって、アルゴリズムの Θ を見つけることが常に可能であるとは限りません。
  • O は、関数の実行の上限を示します。通常、これは人々がアルゴリズムのために計算するものです。そうすることで、彼らは、何があっても、私のアルゴリズムはこれより悪くはありませんが、場合によってはより良くなる可能性があると言っています. たとえば、挿入ソートはO(n^2).
  • O が最良 (最小) の上限を示さないことがあります。それを見つけるのが難しすぎるからです。そのような場合でも、O が助けに来ます。たとえば、UI アプリケーションでサイズ 1000 の入力で動作するアルゴリズムがある場合 (たとえば、0.5 秒の遅延は問題ありません)、アルゴリズムがO(n^2)適切である場合、アルゴリズムの最悪の場合の実行は実際にはそれよりも低くなっています (しかし、それを見つけるのは難しすぎました)。最良の上限は、アルゴリズムの最悪の場合の実行の成長率です。挿入ソートの例では、最悪の場合の実行はΘ(n^2)であるため、アルゴリズムに与えることができる最良の上限は(たとえばO(n^2)とは対照的に) です。O(n^3)
  • Ω は実際にはあまり役に立ちません。私のアルゴリズムがせいぜいこのようなものだとは言いたくありませんが、もっと悪い可能性もあります (それは悪い広告です)。ただし、コンピューターサイエンスでは非常に役立ちます。ほとんどの場合、何かをより良い方法で行うことができないことを証明する. たとえば、 に問題を解決するアルゴリズムがあり、問題を解決するアルゴリズムが であるΘ(n^3)必要があることを証明した場合Ω(n^3)、それは、既に持っているアルゴリズムよりも優れたアルゴリズムが存在することは決してないことを意味します (つまり、他の人にそうしないように伝えます)探さないでください、見つかりません）

理解するのも、自分で発明するのも難しくない O 記法数学がたくさんあります。いくつかの例は次のとおりです。

  • O(f(n)+g(n)) = O(max(f(n),g(n)))
  • O(f(n))+O(g(n)) = O(f(n)+g(n))
  • O(f(n))O(g(n)) = O(f(n)g(n))
  • O(cf(n)) = O(f(n)) c は定数です。

これらのほとんどは、O 表記の定義に入れることですぐに証明できます。

これらのルールの最初のルールは、おそらく最も有用です。アルゴリズムに 2 つのセクションがあり、1 つのセクションでサイズの配列nを 0 に設定し、何かを実行するとO(nlogn)、全体的な順序O(n+nlogn)は単純になりO(nlogn)ます。

これは、数学的に言えば、1000 のO(nlogn)前処理とO(nlogn)問題を解決するアルゴリズムを使用する方が、簡潔なアルゴリズムを使用するよりも優れていることを意味しO(n^1.5)ます。ただし、実際には、必ずしも優れているとは限りません。なぜ聞くの？1つO(nlogn)目は2つ目O(n^1.5)なので、1つ目の方がいいですか？O 表記は、関数の動作を漸近的に示していることを思い出してください。つまり、はい、出力が非常に非常に大きくなる場合、最初のアルゴリズム (1000 の前処理を行うアルゴリズム) の方が優れていますが、実用的な範囲では、nは1000nlognよりもはるかに大きくなる可能性がありますn^1.5。

于 2011-10-09T18:58:12.847 に答える
4

宿題である場合は、ノードが関数呼び出しに必要な操作の複雑さを表す再帰ツリーとして描画することを試みることができます。

編集：下限について、オメガは下限として定義されています。Theta (正確な動作) がある場合は、Omicron と Omega もあります... これらは精度が低くなります。

そう

Theta(n) <=> O(n) AND Omega(n)

ネタバレ

私の記憶が正しければ、これはあなたがそれをどのように解釈するかです...

ツリーがあり、そのルートにはC(ソリューションをマージするための作業) しかなく、2 つのブランチに吐き出す必要があります (再びC作業として)、ノードはn何度も分岐します。

     C
    /|
   C C
  /| |\
 C C C C
/| ......

完全なソリューション

ツリーの深さはnであり、最下部には の2^n複雑さを持つノードがあり、複雑さのCレベルn-1があり、C, 2C, 4C....(2(n-1)*C)合計すると になります。2^n*c

したがって、最終的な複雑さは次のとおり2*(2^n)*Cです。theta(2^n)

于 2011-10-09T18:47:30.460 に答える