關於大樣張問題

下面的陳述是真是假？

所有日誌到基座2

log2n是O的成員（的log（n））

我嘗試：

現在，糾正我，如果我錯了，但我必須找到N（變量）和C（恆定），它要麼證明或反駁這一數值...

一般來說，這似乎是真的：

選擇

n0 = 2, c = 3 -> TRUE 
n1 = 3, c = 3 -> TRUE 
n2 = 4, c = 3 -> TRUE

因此，聲明似乎正不正確，LOGN增加。但是也存在以上陳述永遠不會成立的值：

例如，

無論n的值是否增加，選擇c = 1的結果都大於零。

所以我很困惑，這是否是真的還是假的....

2011-04-19 user559142

我也很困惑:-) – Johan 2011-04-19 10:42:12

你可以只使用一個事實，即產品的對數的因素對數的總和：

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

2011-04-19 10:42:11 NPE

好的，這告訴我這是真的。不幸的是我必須使用上面的方法來證明它。我只是困惑爲什麼某些價值評估是錯誤的。 – user559142 2011-04-19 10:47:17

@ user559142：你所要做的就是顯示條件滿足* c *的一個*值（對於所有足夠大的'n'）。您不必證明（並且通常情況並非如此）該條件適用於* every *'c'。 – NPE 2011-04-19 11:18:50

真的啊！這很容易！非常感謝 – user559142 2011-04-19 11:36:24

回答