2n+5 が O(n²) であることを示せという宿題があります。
これは私が試して解決するためにしたことです：
k = 1 を選択し、n > 1 と仮定したため、f(n)/g(n) = (2n+5)/n² < (2n+5n)/n² = 7n/n² = 7/n
したがって、C は 7/n に等しい したがって、2n+5 <= (7/n)(n²) なので、2n+5 <= 7n となり、すべての n > 1 について真になります。これが、2n+5 が O( である理由です。 n²)。
それが正しいかどうかはわかりませんでした。100% 確信があるわけではありませんが、誰かがそれを確認できれば、それは素晴らしいことです。
また、シータ表記に簡略化するよう求められた別の問題についても混乱しました。
(x 4.2 )/(1+x²)。無限大に評価したばかりなので、それはただの Θ(x 2.2 ) ですか?
また、x³⋅lg(x) どこから始めればいいのかわかりません。
前もって感謝します！
（特にあなたの質問についてのTLDRが最後にあります。big-Oについても少し説明したいと思います）
おそらく、形式主義よりも明白な何か: この O 記法のものは、関数の成長に応じて関数を比較することになっています。多項式をその成長に従って比較する場合、見なければならないのは最高の指数 (つまり、「次数」) だけです。同じ次数であれば、お互いにほぼ同じ速さで成長します。一方の次数が他方よりも高い場合、次数の高い方が他方よりも速く成長します。
したがって、それと中学校の数学から、2n+5 = O(n^2) であることがすぐにわかります。2 次関数 (n^2 の正の係数を持つ) は、ある時点で線形関数を超えるからです。
ここで形式主義に戻ります。また、2 つの関数が「ほぼ同じ速度で」成長するという考えを捉えたいと考えています。たとえば、正の成長のすべての線形関数は、ほぼ同じ速度で成長します。そのために、倍率 c を導入します。f(n) <= c*g(n) の場合、f = O(g) とします。そのスケーリングを使用すると、すべての線形関数が「ほぼ同じ速さで」成長することがすぐにわかります。f(n) = a*n + b と g(n) = k*n + d を使用すると、スケーリング係数を使用して g を再スケーリングできます。 a/k を取得し、a/k * g(n) = a*n + d*a/k; を取得します。そのため、a/k * g(n) と f(n) は同じ速さで成長し、それらの絶対差は一定の値に減少します。
線形および二次関数の場合、それはできません。線形関数をどれだけ再スケーリングしても、二次関数は常により速く成長します。たとえば、派生物からそれを見ることができます。一次関数の微分は定数であり、二次関数の微分は一次関数であるため、二次関数の成長は常に増加しますが、一次関数の成長は同じままです。
big-O 定義の最後の部分は、「一部の n_0 に対してすべての n > n_0 に対して」というビットです。これを行う理由は、g が f よりも速く成長したとしても、最初は f がより高い値を持つ可能性があるためです。たとえば、g(n) = n^2 と f(n) = n + 2^200 を比較してください。最初は、いくらリスケールしても、f(1) は c*g(1) よりも大きくなります。そのようなことに煩わされたくないので、「ある時点で c*g が f より上にあり、その上にとどまっている場合、それは私たちの目的には十分です」と言います。ここで、「(そのような ac が存在する) すべての n > n_0 に対して f <= c*g となる n_0 が存在する」が登場します。
ここで質問に戻ります。すべての n > n_0 に対して 2n+5 <= c*n^2 となるような ac と n_0 があることを示したいとします。ここで確認しなければならないのは、c が関数ではなく NUMBER であることです。そのため、c = 7/n を設定することは問題外です。しかし、実際には任意の正の c を選択して、不等式を解決できるかどうかを確認できます。c = 3 の場合を示します。
2n+5 <= 3*n^2
0 <= 3*n^2 - 2n - 5
3*n^2 - 2n - 5 の根は 10/6 と -1 です。つまり、-1 より前では不等式が成立し、-1 と 10/6 の間では 0 未満になり、10/6 の後では不等式が成立します。再び保持します。これは、10/6 の後の最初の自然数を n_0 として選択することを意味するため、n_0 = 2 が得られます。
x^4.2/(1+x^2) に関して、x > 1 および x^4.2 の場合、0.5*x^2.2 = x^4.2/(2x^2) < x^4.2/(1+x^2) が得られます。 /(1+x^2) < x^4.2/x^2 = x^2.2 すべての正の x。
x^3 lg x については、これで終わりです。これ以上簡単な式はありません。もちろん、対数を使用せずに上限を指定することもできますが、実際に行う必要はありません。