什么是次线性算法？
What are sublinear algorithms?
我的一位伙伴问我以下问题。
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 但是不能，但我不确定我是否完全理解了它。有人能指出我正确的方向吗？
一个函数 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
（次线性）
我想我理解你为什么感到困惑：你 link 的维基百科页面使用 Little-Oh 符号：
Sub-linear time
An algorithm is said to run in sub-linear time (often spelled sublinear time) if 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).
我建议阅读 this answer 以继续学习
我的一位伙伴问我以下问题。
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 但是不能，但我不确定我是否完全理解了它。有人能指出我正确的方向吗？
一个函数 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
（次线性）
我想我理解你为什么感到困惑：你 link 的维基百科页面使用 Little-Oh 符号：
Sub-linear time
An algorithm is said to run in sub-linear time (often spelled sublinear time) if 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).
我建议阅读 this answer 以继续学习