大O符號O（P 1 2日誌P）

Question

請幫我描述和解決爲什麼

Θ（P^2的log P^2）=Θ（P^2日誌P）

我真的很眩暈。

Answer 1

如果x = log p^2表示e^x = p^2。那意味着sqrt(e^x) = p等等e^(x*1/2) = p。所以(log p^2)/2 = log p。這意味着p^2 log p^2 = 2 p^2 log p;因爲這是大θ恆定的乘數可以被丟棄，所以它們是相等的。

Answer 2

日誌（P^2）= 2的log P（如在一般情況下，log (n^m) = m log n）

由於2僅僅是一個常數，我們有Θ（的Log P^2）=Θ（的log P）。因此，我們得到Θ（p^2 log p^2）=Θ（p^2 log p）。

Answer 3

從定義開始總是很好的！ Wiki：

大O符號描述了當 參數朝向特定 值或無窮大的傾向的函數的限制 行爲

限制行爲是相同的爲功能f和g，如果g = C*f 。漸近地他們表現相同。現在到log。 Remeber下式：

日誌 _b^XŶ = Y登錄 _b X

這意味着，它們是不同的僅由恆定，這並不改變limitting行爲。

但重要的是要記住它們的速度和操作量仍然不同（按常量）。

Answer 4

我推測是因爲log（x^n）= nlog（x）。而n是一個常數，因此在大O中不相關。換言之，O（n）= O（2n），因爲當n加倍時，它們都是兩倍。