algorithm - 什么是次线性算法？

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  

(次线性)