关于大样张问题

Question

我有以下问题：

下面的陈述是真是假？

所有日志到基座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的值是否增加，选择c = 1的结果都大于零。

所以我很困惑，这是否是真的还是假的....

Answer 1

你可以只使用一个事实，即产品的对数的因素对数的总和：

log(2n) = log(2)+log(n) = O(log(n))