大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加倍时，它们都是两倍。