如果g(n) = sqrt(n)^sqrt(n)，g(n) = O(2^n)的复杂度是多少？
If g(n) = sqrt(n)^sqrt(n), does the complexity of g(n) = O(2^n)?
如果g(n) = sqrt(n)sqrt(n), g(n) = O(2n)?
感谢任何帮助。
比较两个指数函数的一个有用技巧是让它们具有相同的基数：
√n√n = (2lg √n)√n = 2√n lg √n
现在你正在比较 2√n lg √n 和 2n，希望从中很容易看出前者的函数没有后者增长得快，所以√n√n = O(2n)确实成立。
可以假设 O(log n) < O(sqrt(n)) (Order of common functions - wikipedia)
转换工作如下：
sqrt(n)^sqrt(n) 2^n # a^b = e^(ln(a) * b)
e^(ln(sqrt(n)) * sqrt(n)) e^(ln(2) * n) # if e^a < e^b, then a < b
ln(sqrt(n)) * sqrt(n) ln(2) * n # / sqrt(n)
ln(sqrt(n)) ln(2) * sqrt(n) # ln(a^b) = b * ln(a)
0.5 ln(n) ln(2) * sqrt(n) # ln(a) / ln(b) = log(a base b)
0.5 log(n base 2) sqrt(n) # base and constant factor don't matter
log(n) sqrt(n)
为了简单起见，我省略了复杂性-类。应从下到上阅读以上内容以获得适当的证明。
其他证明简短而漂亮，但这里有更详细的证明，涉及大 O 符号的定义和所需限制的计算。
一个函数 g(n) 的上界是另一个函数 f(n) 的大 Oh 符号 (g(n) = O(f(n))) 如果它满足
(source)
输入函数，我们必须计算
首先对 g(n) 项进行一些代数推敲。根据根身份，它认为sqrt(n) = n^(1/2)。此外，它认为 (x^a)^b = x^(a*b)。有了那个：
此外，2^n由对数恒等式exp(log( 2^n ))，然后log(a^b) = b*log(a)我们有2^n = exp(log( 2^n )) = exp(n * log(2))。同样可以应用到n^(1/2 sqrt(n))，它变成exp(log( n^(1/2 sqrt(n)) = exp(1/2*sqrt(n)*log(n))。所以现在我们有
此时我们可以比较指数的增长情况，即比较
该限制为 0，因为 const * n 比 sqrt(n)*log(n) 增长得更快。反过来，这可以显示为明确计算限制。将 1/2 和 log2 放在分母中。由于n = sqrt(n) * sqrt(n)，我们可以将其简化为：
这个限制确实是零，因为平方根比对数增长快 Orders of common functions。因此，较低函数的指数比较高函数的指数增长得更快。因此g(n) = O(2^n)被第一个定理严格证明。
如果g(n) = sqrt(n)sqrt(n), g(n) = O(2n)?
感谢任何帮助。
比较两个指数函数的一个有用技巧是让它们具有相同的基数：
√n√n = (2lg √n)√n = 2√n lg √n
现在你正在比较 2√n lg √n 和 2n，希望从中很容易看出前者的函数没有后者增长得快，所以√n√n = O(2n)确实成立。
可以假设 O(log n) < O(sqrt(n)) (Order of common functions - wikipedia)
转换工作如下：
sqrt(n)^sqrt(n) 2^n # a^b = e^(ln(a) * b)
e^(ln(sqrt(n)) * sqrt(n)) e^(ln(2) * n) # if e^a < e^b, then a < b
ln(sqrt(n)) * sqrt(n) ln(2) * n # / sqrt(n)
ln(sqrt(n)) ln(2) * sqrt(n) # ln(a^b) = b * ln(a)
0.5 ln(n) ln(2) * sqrt(n) # ln(a) / ln(b) = log(a base b)
0.5 log(n base 2) sqrt(n) # base and constant factor don't matter
log(n) sqrt(n)
为了简单起见，我省略了复杂性-类。应从下到上阅读以上内容以获得适当的证明。
其他证明简短而漂亮，但这里有更详细的证明，涉及大 O 符号的定义和所需限制的计算。
一个函数 g(n) 的上界是另一个函数 f(n) 的大 Oh 符号 (g(n) = O(f(n))) 如果它满足
(source)
输入函数，我们必须计算
首先对 g(n) 项进行一些代数推敲。根据根身份，它认为sqrt(n) = n^(1/2)。此外，它认为 (x^a)^b = x^(a*b)。有了那个：
此外，2^n由对数恒等式exp(log( 2^n ))，然后log(a^b) = b*log(a)我们有2^n = exp(log( 2^n )) = exp(n * log(2))。同样可以应用到n^(1/2 sqrt(n))，它变成exp(log( n^(1/2 sqrt(n)) = exp(1/2*sqrt(n)*log(n))。所以现在我们有
此时我们可以比较指数的增长情况，即比较
该限制为 0，因为 const * n 比 sqrt(n)*log(n) 增长得更快。反过来，这可以显示为明确计算限制。将 1/2 和 log2 放在分母中。由于n = sqrt(n) * sqrt(n)，我们可以将其简化为：
这个限制确实是零，因为平方根比对数增长快 Orders of common functions。因此，较低函数的指数比较高函数的指数增长得更快。因此g(n) = O(2^n)被第一个定理严格证明。