什么是次线性算法？

本文介绍了什么是次线性算法？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我的一位同事问了我以下问题。

Which of the following expressions is not sublinear? O(log log n) O(n) O(logn) O(root(n))

我已经通过了en.wikipedia/wiki/Time_complexity#Sub-linear_time，但不能，但我不确定我是否完全理解了它。有谁能给我指个方向吗？

推荐答案

一个函数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

(次线性)