artificial-intelligence - f(n) が O(2^n) であることの証明

Question

Big-O の定義を使用して f(n) が O(n) または O(n^2) であることを証明する方法は理解していますが、O(2^n) で迷子になり、2^n +n の証明を手伝ってもらえますか? ^3 + 30 は O(2^n) pls ですか? Bsc AI Yr1 すべてが大好きですが、複雑さが私のお尻を蹴っています!

Answer 1

Big O表記法は、関数が何らかの値に近づくときの関数の動作を定義します。多くの場合、無限大と言いますが、一般的には「任意の数」で十分です。

したがって、あなたは数学的限界の世界にいます。ここではMathSEが役立ちますが、あなたのケースを考えてみましょう。それを示すために：

O(2^n +n^3 + 30) == O(2^n)

n多数に2^n +n^3 + 30なる傾向があるので、に向かう傾向があることを示す必要があり2^nます。調べてみると、が10のときnはn^31000であり、すでに30よりはるかに大きい（そして成長nするにつれて成長する）ことがわかります。この時点で2^nは1024なので、と同じオーダーですがn^3、大きくなります。一度nは100、n^3は100万、2^nはこの数の5倍です（1 x 10^30）...非常に明確なので、最初の用語は他の用語を上回り、n「任意に大きい」とは呼ばれません。

ですから、検査によって、私たちはそれを知っています

O(2^n +n^3 + 30) == O(2^n)

Answer 2

まあ、それはあなたが使用できるツールに依存します。一見したところ、それはかなり明白なので、おそらく証明をさらに深める必要があります。

基本的に、n^3 は 2^n に比べて途方もなく小さいので、n^3 ~ o(2^n) となります。

定数 30 についても同じです。

そう

2^n + n^3 + 30 ~ 2^n + o(2^n) ~ O(2^n)定義により。

証明として不十分な場合は、次のことを証明できます。

limit n^3/2^n (when n-> infinity) = 0

Answer 3

それを証明してn^3 < 2^n for some n > n0ください (誘導によって、またはいくつかの典型的な数学の演習を見て、それを参照してください。最小の n0 を見つける必要はなく、任意の n0 だけを見つける必要があります)。

次に、この結果で を|2^n + n^3 + 30| <= |2^n +2^n + 2^n|示し、2 と 4 の間の見栄えの良い c を見つけて、最後の項が より小さいことを示しc*|2^n|ます。

このすべての後、すべてを一緒に書くと、次のようなものになるはずです|2^n +n^3 + 30| <= ... <= c*|2^n| for n > <n0> and c=<value>（<n0>そして<value>、あなたが終わった後、いくつかの数字になるはずです）。これが定義です。

Answer 4

宿題のように聞こえるので、私はあなたのために問題を解決するつもりはありません。しかし、私はあなたがすでに解決方法を知っている問題を解決し、この問題も例外ではないことをあなたに納得させようとします.

そう。f(n) と呼ばれるある関数が、g(n) と呼ばれる他の関数の Big-Oh に属していることを証明しようとしているときのことを思い出してください。一定の係数までは証明しようとしており、n が大きくなると、f(n) が g(n) より悪くなることはありません。これを行うには、c と n ₀という 2 つの数値を選択します。最初の c は、前に述べた「定数係数」です。次のように f(n) を g(n) に関連付けます。

f(n) ≤ cg(n) すべての n ≥ n _{0について}

問題は、c と n0 が一意ではないということです。多くの場合、一方をほぼ任意に選択し、単純な代数を使用して他方の値を計算できます。それでは、これを試してみましょう

f(n) = n² + 5n + 10

g(n) = n²

まず、定数係数 c に従って関係を設定します。

n² + 5n + 10 ≤ c n²

ここで、n の他の関数に関連する c を単独で取得したいので、n² を両側から除算します。

1 + 5/n + 10/n² ≤ c

n のどの値 (これを n ₀と呼びます) が、n のすべての大きな値に対してそれを真にするかを知りたいのです。さて、ac を選んで n について解くか、n ₀を選んで c について解くことができます。あまり重要ではありませんが、n ₀ = 1 を選択して、n が表示されているすべての場所にプラグインして、何が起こるかを見て みましょう。

1 + 5/1 + 10/1 = 1 + 5 + 10 = 16 ≤ c

これが私たちの答えです。c を 16 とすると、n が 1 より大きい (つまり、n ₀ = 1) ときはいつでも、f(n) は g(n) よりも小さくなります。

さて、解決しようとしている問題でそれを行うことができますか? ええと...なぜですか？f(n) と g(n) の 2 つの関数があります。解決方法を知っている問題とまったく同じ関係を証明しようとしています。変更されたのは、n の多項式から n の指数関数 (および混合されたもの) への関数のタイプだけです。しかし、それは問題でしょうか? さて、代数は少し違うように見えますが、それでどうでしょうか? 代数です。