在大O符号中,O((log n)^k) = O(log n)
,其中k
是一些常数(例如对数循环的数量),是真的吗?
我的教授告诉我这个陈述是正确的,但他说它将在课程后面证明。我想知道你们中是否有人能够证明它的有效性,或者是否有任何链接可以确认它是否是真的。
在大O符号中,O((log n)^k) = O(log n)
,其中k
是一些常数(例如对数循环的数量),是真的吗?
我的教授告诉我这个陈述是正确的,但他说它将在课程后面证明。我想知道你们中是否有人能够证明它的有效性,或者是否有任何链接可以确认它是否是真的。
(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网站表达爱意。这里是一个链接。去让这个新地方成为现实!
您确定他不是指O(log n^k)吗?因为这等于O(k*log n)= k*O(log n)= O(log n)。
O(log n)是一类函数。你不能对它执行诸如^k之类的计算。因此,术语O(log n)^k对我来说甚至看起来都不合理。