在大 O 表示法中O((log n)^k) = O(log n)，k某个常数（例如，对数 for 循环的数量）在哪里，是真的吗？
我的教授告诉我这个说法是正确的，但是他说这将在课程的后期得到证明。我想知道你们中的任何人是否可以证明它的有效性或有一个链接我可以确认它是否属实。
6980 次
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? )
编辑：
在相关的说明中，任何认为这个问题有帮助和/或有趣的人都应该对新的“计算机科学”StackExchange 站点表现出一些热爱。这是一个链接。去把这个新地方变成现实吧！
于 2012-01-10T20:12:18.923 回答
5
你确定他不是指 O(log n^k)，因为这等于 O(k*log n) = k*O(log n) = O(log n)。
于 2012-01-10T19:27:41.660 回答
-1
O(log n ) 是一类函数。您不能对其执行 ^ k等计算。因此，术语 O(log n )^ k对我来说甚至看起来都不合理。
于 2012-01-10T19:27:47.153 回答