无法用对数和分数计算函数的增长率
Can't calculate growth rate of function with log and fraction
我正在尝试解决下图中有关获取增长率的问题，但我做不到。
据我之前的了解，如果有分数，我们通常不关心分母，而是考虑分子部分，即“2+3n”。
因此，从我的角度来看，答案是“2+3n < 2n+3n = 5n with witness c=5 and k=1”或“2+3n < n+3n = 4n with witness c=4和 k=2”，两者都导致 O(n)。
但是，根据答案，这是不正确的。
你能展示我如何得到那个答案的整个计算步骤吗，Big-theta(root(n)/log(n))？
您只需关注big O notation definition。对于这些，我喜欢使用 big O 的极限定义：
f(n) is in O(g(n)) if and only if:
lim n-> infinity |f(n) / g(n)| < infinity
然后将其应用于您的问题：
f(n) = (2+3n)/(5sqrt(n)(1+4logn))
g(n) = sqrt(n) / log(n)
然后对结果做一些代数运算：
lim n-> infinity: |f(n)/g(n)| =
= |(2+3n)log(n)/(5sqrt(n)(1+4logn)sqrt(n))| <=
<= |5nlog(n)/5sqrt(n)(1+4logn)sqrt(n))| =
= |nlogn/ (sqrt(n) * sqrt(n) * (1+4logn)| =
= |nlogn / n(1+4logn)| =
= |logn / (1+4logn)| <= |logn / 4logn| = 1/4 < infinity
由此，以及大O符号的定义，证明了f(n)在O(g(n))中。您可以类似地显示 big Omega，通过显示 lim n->infinity |g(n)/f(n)| < infinity，通过显示它同时是 O(g(n)) 和 Omega(g(n))，您可以得出结论这是紧束缚 (Theta(g(n))。
我正在尝试解决下图中有关获取增长率的问题，但我做不到。
据我之前的了解，如果有分数，我们通常不关心分母，而是考虑分子部分，即“2+3n”。
因此，从我的角度来看，答案是“2+3n < 2n+3n = 5n with witness c=5 and k=1”或“2+3n < n+3n = 4n with witness c=4和 k=2”，两者都导致 O(n)。
但是，根据答案，这是不正确的。
你能展示我如何得到那个答案的整个计算步骤吗，Big-theta(root(n)/log(n))？
您只需关注big O notation definition。对于这些，我喜欢使用 big O 的极限定义：
f(n) is in O(g(n)) if and only if:
lim n-> infinity |f(n) / g(n)| < infinity
然后将其应用于您的问题：
f(n) = (2+3n)/(5sqrt(n)(1+4logn))
g(n) = sqrt(n) / log(n)
然后对结果做一些代数运算：
lim n-> infinity: |f(n)/g(n)| =
= |(2+3n)log(n)/(5sqrt(n)(1+4logn)sqrt(n))| <=
<= |5nlog(n)/5sqrt(n)(1+4logn)sqrt(n))| =
= |nlogn/ (sqrt(n) * sqrt(n) * (1+4logn)| =
= |nlogn / n(1+4logn)| =
= |logn / (1+4logn)| <= |logn / 4logn| = 1/4 < infinity
由此，以及大O符号的定义，证明了f(n)在O(g(n))中。您可以类似地显示 big Omega，通过显示 lim n->infinity |g(n)/f(n)| < infinity，通过显示它同时是 O(g(n)) 和 Omega(g(n))，您可以得出结论这是紧束缚 (Theta(g(n))。