Big Oh 表示法 O((log n)^k) = O(log n)?

问题描述 投票:0回答:3

用大 O 表示法是

O((log n)^k) = O(log n)
,其中
k
是某个常数(例如对数 for 循环的数量),对吗?

我的教授告诉我这个说法是正确的,但他说这将在课程稍后得到证明。我想知道你们中是否有人可以证明其有效性或有一个链接让我可以确认它是否属实。

big-o proof
3个回答
8
投票

(1) 确实,O(log(n^k)) = O(log n)。

(2) O(log^k(n)) (也写作 O((log n)^k)) = O(log n) 是错误的。

观察结果:(1) 已被 nmjohn 证明。

练习:证明(2)。 (提示:f(n) = log^2 n 是 O(log^2 n)。是 O(log n) 吗?足够大的常数 c 是多少,使得对于所有大于 n0 的 n,c log n > log^2 n?)

这更像是一个计算机科学问题。有关此主题的未来问题应在 SE 网站上询问。


5
投票

你确定他说的不是 O(log n^k),因为它等于 O(k*log n) = k*O(log n) = O(log n)。


-1
投票

O(log n) 是一类函数。您无法对其执行诸如 ^k 之类的计算。因此,术语 O(log n)^k 对我来说甚至看起来都不合理。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.