什么是次线性算法？

Question

我的一位同事问我以下问题.

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但不能,但我不确定我是否完全了解它.有人能指出我正确的方向.

Answer 1

假设函数f(x)比另一个函数g(x)增长得快,如果它们的比率x接近无穷大的极限达到某个正的有界数,如下面的定义所示.

在次线性的情况下,我们想要证明函数比c*n增长得慢,其中c是一些正数.

因此,对于列表中的每个函数f(n),我们需要f(n)与(c*n)的比率.如果限制为0,则表示函数f(n)是次线性的.否则它以相同(近似)的速度增长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  

(次线性)

Answer 2

我想我明白你为什么感到困惑:你链接的维基百科页面使用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).

我建议您阅读此答案以继续学习