什么是次线性算法?

我的一位同伴被问到了下面的问题。

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

满足你选择的每一个ky=xk=1将证明你是错误的,而小的哦符号要求每个k满足这个表达式。

任何O(n)函数都不在o(n)中。 因此你的非次线性表达式是O(n)。

我建议阅读这个答案继续你的学习

链接地址: http://www.djcxy.com/p/39885.html

上一篇: What are sublinear algorithms?

下一篇: Difference between lower bound and tight bound?