什么是次线性算法?
我的一位同伴被问到了下面的问题。
Which of the following expressions is not sublinear?
O(log log n)
O(n)
O(logn)
O(root(n))
我已经通过https://en.wikipedia.org/wiki/Time_complexity#Sub-linear_time,但不能,但我不知道我已经完全理解它。 有人能指出我的方向是正确的吗?
如下面的定义所示,函数f(x)据说比其他函数g(x)增长得更快,如果它们的比率在x接近无穷大时的极限值达到某个正数有界数。
在次线性的情况下,我们想要证明函数的增长比c * n慢,其中c是一些正数。
因此,对于每个函数f(n),在你的列表中,我们需要f(n)与(c * n)的比值。 如果极限是0,这意味着函数f(n)是次线性的。 否则它会以相同(近似)的速度增长或更快。
lim n->inf (log log n)/(c*n) = 0 (via l'Hopital's)
(次线性)
lim n->inf (n)/(c*n) = 1/c != 0
(线性)
lim n->inf (log n)/(c*n) = 0 (via l'Hopital's)
(次线性)
lim n->inf (sqrt(n))/(c*n) = 0
(次线性)
我想我明白你为什么感到困惑:你链接的维基百科页面使用Little-Oh符号:
亚线性时间
如果T(n)= o(n),则称算法在亚线性时间(通常拼写为次线性时间)
注意T(n)= o(n)比说T(n)= O(n) 要强 。
特别是对于O(n)中的函数,你不能总是有不等式
f(x) < k g(x) for all x > a
满足你选择的每一个k
。 y=x
和k=1
将证明你是错误的,而小的哦符号要求每个k
满足这个表达式。
任何O(n)函数都不在o(n)中。 因此你的非次线性表达式是O(n)。
我建议阅读这个答案继续你的学习
链接地址: http://www.djcxy.com/p/39885.html