本文介绍了什么是次线性算法?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我的一位同事问了我以下问题。
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(次线性)
更多推荐
什么是次线性算法?
发布评论