这个表达式是什么 f(n) = 2O(n) 意思是,以一种完全正式的方式?
最佳答案
语句f(n) = 2^O(n)
等价于
log_2(f(n)) = O(n)
(实际上,任何对数都可以),所以这意味着存在一些常量 C > 0
使得
log_2(f(n)) <= C*n <=> f(n) <= 2^(C*n)
对于所有足够大的n
。现在,ab*c = (ab)c,所以另一种表达方式是
f(n) = O(b^n)
对于某些 b > 0
。这个 b
可能是 1.5
,或者 4
,或者 1000000000000
,所以它不会告诉你太多。它给你的只是 f
是指数级的,所以它比 O(n!)
渐近更好,但它并没有告诉你它是否非常糟糕,糟糕,真的糟糕或真正灾难性的糟糕。
关于big-o - 指数中大O的含义,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8637245/