我有以下问题:
下列说法正确还是错误？
所有日志到 base 2
log2n 是 O(log(n)) 的成员
我的尝试:
- log2n - clogn <= 0
- log2 + logn - clogn <= 0
- 1 + logn(1-c) <= 0
如果我错了请纠正我，但我必须找到 n(变量)和 c(常量)的值来证明或反驳这个...
通常这似乎是真的:
选择
n0 = 2, c = 3 -> TRUE
n1 = 3, c = 3 -> TRUE
n2 = 4, c = 3 -> TRUE
因此，该陈述似乎是正确的，logn 随着 n 的增加而增加。但也有一些值是上述陈述永远不会成立的:
例如
无论 n 的值如何增加，选择 c = 1 的结果都大于零。
所以我很困惑这是真的还是假的....
最佳答案
您可以只使用乘积的对数是因子的对数之和这一事实:
log(2n) = log(2)+log(n) = O(log(n))
关于algorithm - 关于大o证明的问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5715111/