什么是子线性算法？

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)

（（sublinear）

lim n->inf (n)/(c*n) = 1/c != 0

（（线性）

lim n->inf (log n)/(c*n) = 0 (via l'Hopital's)

（（sublinear）

lim n->inf (sqrt(n))/(c*n) = 0  

（（sublinear）

Answer 2

[我想我理解您为什么感到困惑：您链接的维基百科页面使用Little-Oh表示法：

次线性时间

如果T（n）= o（n），则算法在亚线性时间（通常是拼写的亚线性时间）中运行

请注意，与说T（n）= O（n）相比，T（n）= o（n）是一个[[stronger要求。

特别是对于O（n）中的函数，不能总是不等式

f(x) < k g(x) for all x > a

对于您选择的每个k都满意。 y=x和k=1将证明您是错误的，并且点点滴答声要求每个k都满足该表达式。在o（n）中，
任何O（n）函数也是
not

。因此，您的非次线性表达式为O（n）。我建议阅读this answer以继续学习