无法计算函数的增长率
Can't calculate growth rate of function
您好，我正在尝试解决上图中的问题，但我做不到。
特别地，我的问题是关于图像中的 C(n)，最后我得到了“7logn + n^(1/3)”。
我们知道+号的左边，“7logn<=n for all n>7 (witness c=1, k=7)”，+号的右边，"n^(1/3)<=n"。
从我的角度来看，+号之间的两边都是O(n)，因此整个C(n)是O(n)。
但为什么答案是 Big-theta(n^1/3)？
仅当 log 是以 2 为底的对数时才成立（那么 log(8) = 3，因为 2^3 = 8）。
8^(log(n)/9) = (8^log(n))^(1/9) = (n^log(8))^(1/9) = (n^3 )^(1/9) = n^(3 * 1/9) = n^(1/3)
n^(1/3) 与 n 的 3 次根相同。
它是 O(n^(1/3)) 而不是 O(log(n)) 因为前一项增长得更快：
n 的极限为 log(n) / (n^(1/3)) 的无穷大等于 0。如果您必须切换表达式以获得 0，那么另一个会增长得更快。例如。 n + log(n) 将是 O(n) 因为 n 增长得更快，不要与 n * log(n) 混淆 O(n * log(n)).
您好，我正在尝试解决上图中的问题，但我做不到。
特别地，我的问题是关于图像中的 C(n)，最后我得到了“7logn + n^(1/3)”。
我们知道+号的左边，“7logn<=n for all n>7 (witness c=1, k=7)”，+号的右边，"n^(1/3)<=n"。
从我的角度来看，+号之间的两边都是O(n)，因此整个C(n)是O(n)。
但为什么答案是 Big-theta(n^1/3)？
仅当 log 是以 2 为底的对数时才成立（那么 log(8) = 3，因为 2^3 = 8）。
8^(log(n)/9) = (8^log(n))^(1/9) = (n^log(8))^(1/9) = (n^3 )^(1/9) = n^(3 * 1/9) = n^(1/3)
n^(1/3) 与 n 的 3 次根相同。
它是 O(n^(1/3)) 而不是 O(log(n)) 因为前一项增长得更快：
n 的极限为 log(n) / (n^(1/3)) 的无穷大等于 0。如果您必须切换表达式以获得 0，那么另一个会增长得更快。例如。 n + log(n) 将是 O(n) 因为 n 增长得更快，不要与 n * log(n) 混淆 O(n * log(n)).