>Problem: n^4 + 100n^2 + 50.
>Solution given: n^4 + 100n^2 + 50 <= 2n^4 for all n>=1
> n^4 + 100n^2 + 50 = O(n^4) with c=2 and n0 = 100
しかし、n が 1 の場合、上記の関数は "4+100+50 <= 2" になり、正しくありません。この問題の正しい上限を導き出すにはどうすればよいですか、または与えられた解が間違っているかどうかを教えてください。
問題は、Java で簡単に作成されたデータ構造とアルゴリズムによるものです。
解決策を述べる正しい方法は
n^4 + 100n^2 + 50 <= c*n^4 for all n>=n0 with c=2 and n0 = 100
=> n^4 + 100n^2 + 50 = O(n^4)
最小の成長率を見つける必要がありますg(n)。
c g(n) >= f(n) for n>=k.
c と k の定数値については、上記の式が成り立ちます。n のより低い値は考慮しません。これはg(n)、 の値が小さい場合nは重要ではないことを意味します。の値が大きい場合n、g(n)は の最大成長率になりf(n)ます。
ここ、f(n)= n^4 + 100 n^2 + 50
nが非常に大きい場合、g(n) = n^4
とを見つけcてk、そのようにc n^4 >= n^4 + 100 n ^2 + 50
100 n^2破棄すると、項とが低下し50ます。cあるべきだと言えます2。
2 n^4 >= n^4 .
の値を見つけるには、と をk代入してみてください。n^2 = tn^4 = t^2c=2
2t^2 >= t^2 + 100t + 50
t^2 >= 100t +50
、、、、、、、およびの値を入力tし始めると、12345678910t^2 =100
で10、私はまだ持っています
100,00 <= 100, 00 +50
でt=11、そしてt^2 = 121、私は以下を持っています
14,641 >= 12150.
だから私のk意志です11。
他の方程式についても同様に、f(n) = 3n +8
g(n)となりますn。以下が であるように を検索cします。ktrue
c.g(n) >= f(n)
4n>=3n+8、定数を破棄8して find 、定数を式にc挿入して find に戻します。8k
k=8には があります32>=32。