私は大きな-O表記

を使用して複雑さを決定するにはどうすればよい

何が必要なのは、ここではいくつかの例があり、あなたは私がビッグ-O表記使用して、その複雑さを見つけることを願って、それを決定する方法についての説明を次のとおりです。私は大きな-O表記

For each of the following, find the dominant term(s) having the sharpest increase in n and give the time complexity using Big-O notation. 
Consider that we always have n>m. 

Expression Dominant term(s) O(…) 
5+ 0.01n^3 + 25m^3 
500n +100n^1.5 + 50nlogn 
0.3n+ 5n^1.5 +2.5n^1.75 
n^2logn +n(log2m)^2  
mlog3n +nlog2n 
50n+5^3 m + 0.01n^2

出典

2016-04-14 Anonymous

Big Oの説明がいくつかありますが、読んだり読んだりしたりすることはできません。 [Big O、あなたはどのように計算しますか？]（http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it?rq=1）と[Big O ]（http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o?rq=1）。残りのポーズされた質問は、あなたの宿題のように見えるものをここの誰かがすることです。 – KevinO

理論的な質問として、コンピュータサイエンスなどのサイトに属しているため、この質問を議論の対象外としています.SE –

かなりシンプルです。

nが（無限に向かって）大きくなると、式の一部が無意味になるので、それらを削除します。

また、表記は相対論的で絶対的なものではなく、スケールがないことを意味しているので、定数は無意味なので削除してください。

例：100 + 2*n。低い数値では100が結果の主な寄稿者ですが、nが増加すると無意味になります。スケールがないので、nと2nは同じもの、つまり線形曲線なので、結果はO(n)です。

それとも別の方法を言った、あなたはこのグラフからの発現における最も極端なカーブを選択します。 http://bigocheatsheet.com/img/big-o-complexity.png

をのは、あなたの第二の例を見てみましょう：500n +100n^1.5 + 50nlogn
第一部分がO(n)です。
第2部はO(n^1.5)です。
第3部はO(nlogn)です。
最も速い上昇曲線はO(n^1.5)です。これが答えです。

出典

2016-04-14 16:49:12 Andreas

詳細な回答をいただきありがとうございます。あなたが見ることができるように、他の例があります。ここには異なる型があり、別の変数[m]があります。それ以外の場合はどうすれば計算できますか？再度、感謝します。 –

私はあなたのためにすべての宿題をするつもりはありません。たぶんこのセクションを読むべきです：https://en.wikipedia.org/wiki/Big_O_notation#Properties – Andreas

@Moudi他の変数は、同じルールに従って、独自の次元です。したがって、最初のものはO（n^3 + m^3） – Carlos

答えて

関連する問題