我需要推导出这个表达式的 Big-O 复杂度：
c^n + n*(log(n))^2 + (10*n)^c
其中 c 是常数，n 是变量。
我很确定我了解如何单独推导出每个术语的 Big-O 复杂性，我只是不知道当这些术语像这样组合时 Big-O 复杂性如何变化。
想法？
任何帮助都会很棒，谢谢。
问问题
1472 次
3 回答
14
答案取决于 |c|
如果 |c| <= 1 它是 O(n*(log(n))^2)
如果 |c| > 1 它是 O(c^n)
于 2010-02-04T05:02:26.790 回答
9
O() 表示法考虑最高项；考虑一下哪一个将主导非常非常大的n.
在你的情况下，最高期限c^n实际上是；其他的基本上是多项式的。所以，它是指数级的复杂性。
于 2010-02-04T04:51:12.060 回答
4
在典型用法中，不直接使用 O 符号的正式定义；相反，函数 f(x) 的 O 表示法是通过以下简化规则导出的：
- 如果 f(x) 是多项之和，则保留增长率最大的一项，而忽略其他所有项。
- 如果 f(x) 是多个因子的乘积，则省略任何常数（乘积中不依赖于 x 的项）。
于 2010-02-04T04:52:06.160 回答