如果某个k 的运行时间为O(n k),则算法在多项式时间内运行.但是,我也看到多项式时间定义为时间n O(1).
我对此有一些疑问:
谢谢!
tem*_*def 10
如果有"运行时为O(n)"或"运行时为O(n 2)" 这样的表达式,则O(n)和O(n 2)项不是实际函数.相反,它们是一些具有某些属性的其他函数的占位符.例如,请接受以下声明:
算法的运行时间为O(n)
这句话的确意味着
有一些函数f(n),其中算法的运行时间为f(n),f(n)= O(n)
例如,如果函数的实际运行时间为137n + 42,则语句"算法的运行时为O(n)"为真,因为有一些函数(即f(n)= 137n + 42)其中运行时的运行时间为算法是f(n)和f(n)= O(n).
鉴于此,让我们考虑一下"算法的运行时间是否为O(1) "的含义.这个陈述相当于
有一些函数f(n),其中算法的运行时间是n f(n)和f(n)= O(1)
既然我们已经明确了术语,那究竟是什么意思呢？直观地,如果函数最终从某个常数开始与上面有界,则函数是O(1).因此,一旦n变得足够大,任何函数f(n)的O(1)必须满足f(n)≤k.因此,至少在直觉上,n O(1)意味着"n被提升到最多k的某个幂",这听起来像多项式函数的定义.
当然,还有那些常数因素的讨厌问题.函数137n 3肯定是O(n 3),但它在前面有一个巨大的常数项.另一方面,如果我们具有n O(1)形式的函数,则在n 3前面没有常数项.我们该如何处理？
这是我们可以通过数学变得可爱的地方.在137n 3的情况下,注意当n> 1时,我们有
137n 3 = n log n 137 n 3 = n 3 + log n 137
请注意,此为n提高到日志的功率ñ 137虽然它看起来像功能日志ñ 137随n变大,它实际上有相反的行为:它降低了正增长.这样做的原因是我们可以使用基本公式的更改来重写log n 137 as
log n 137 = log 137/log n
当log n减少时,长期明显减少.因此,表达式3 + log n 137最终被某个常数从上面限制,所以它是O(1).
使用这种技术,可以将O(n k)转换为n O(1),方法是选择n的指数为k加上大n中出现的n k项前面的常数因子的log base n -O表示法.类似地,我们可以通过选择k作为任何常数来从n O(1)转换回O(n k),该常数上限由n的指数中的O(1)项隐藏的函数.
希望这可以帮助!