大O符号O(P 1 2日志P)
答
如果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
;因为这是大θ恒定的乘数可以被丢弃,所以它们是相等的。
答
日志(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)。
答
从定义开始总是很好的! Wiki:
大O符号描述了当 参数朝向特定 值或无穷大的倾向的函数的限制 行为
限制行为是相同的为功能f
和g
,如果g = C*f
。渐近地他们表现相同。现在到log
。 Remeber下式:
日志 bXŶ = Y登录 b X
这意味着,它们是不同的仅由恒定,这并不改变limitting行为。
但重要的是要记住它们的速度和操作量仍然不同(按常量)。
答
我推测是因为log(x^n)= nlog(x)。而n是一个常数,因此在大O中不相关。换言之,O(n)= O(2n),因为当n加倍时,它们都是两倍。
@Klaus Byskov Hofmann哈哈。今天最好的笑声:) – alex 2011-01-24 12:29:04