如果我对递归关系有以下封闭形式的解决方案，如何在大 O 下简化它：
f(n) = 3^n + n.9^n
我会冒险猜测：
f(n) 是 O(9^n) 的成员 -> 我不确定这是否正确？有人可以让我知道如何在大 O 下简化上述方程，并说明您使用的规则...
提前致谢
问问题
1036 次
2 回答
5
http://en.wikipedia.org/wiki/Big_O_notation
如果 f(x) 是多项之和，则保留增长率最大的一项，而忽略其他所有项。
所以O(n * 9^n)，假设与n.9^n你的意思n * 9^n。
于 2011-04-18T10:42:28.360 回答
3
对您有帮助的简单关系是：
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 < Epsilon <1。
请参阅wiki 中的 big O 以获得更好的理解
于 2011-04-18T10:43:50.910 回答