大O符号中的O((log n)^k) = O(log n)吗？（涉及IT技术）

Question

6

在大O符号中，O((log n)^k) = O(log n)，其中k是一些常数（例如对数循环的数量），是真的吗？

我的教授告诉我这个陈述是正确的，但他说它将在课程后面证明。我想知道你们中是否有人能够证明它的有效性，或者是否有任何链接可以确认它是否是真的。

- user1084113

2

最好在http://math.stackexchange.com上询问此问题。 - Michael Piefel

k 是什么？一个常数吗？还是描述问题规模的另一个参数？如果将 k 应用于整个对数，您是否打算写成 O((log n) ^ k)？ - Michael Piefel

更改已经完成，k是一个常数。 - user1084113

@user1084113：有可能是你没有正确理解你的教授，或者他犯了错误。无论哪种情况，请查看我的答案以获得澄清。 - Patrick87

3个回答

5

您确定他不是指O(log n^k)吗？因为这等于O(k*log n)= k*O(log n)= O(log n)。

- nmjohn

问题出在两个对数循环上，他明确地放置了括号以表示k应用于整个对数。 - user1084113

-1

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

- Michael Piefel

这是一个答案，@Patrick87。它的字面意思是“你的问题是虚假的，无法回答”，当时确实如此。 - Michael Piefel

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Patrick87 · Accepted Answer

（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网站表达爱意。这里是一个链接。去让这个新地方成为现实！