algorithm - Big O のルール - 質問

Question

再帰関係に対して次の閉じた形式のソリューションがある場合、大きな O の下でそれを単純化するにはどうすればよいですか。

f(n) = 3^n + n.9^n

私は推測を危険にさらします：

f(n) は O(9^n) のメンバーです -> これが正しいかどうかわかりませんか? 誰かが大きなOの下で上記の方程式を単純化する方法と、どのルールを使用したかを教えてください...

前もって感謝します

score 5 · Accepted Answer

f（x）がいくつかの項の合計である場合、成長率が最大の項が保持され、他のすべての項は省略されます。

だから、あなたと一緒に意味するO(n * 9^n)と仮定します。n.9^nn * 9^n

score 3 · Accepted Answer

あなたを助ける簡単な関係は次のとおりです。

O(1) < O(log(N) < O(N^Epsilon)<O(N)<O(N logN)<O(N^c)<O(c^n)<O(n!)<O(n^n)

c >1 および 0 < イプシロン <1 の場合。

理解を深めるために wiki で大きな O を参照してください

2 に答える 2