algorithm - 如果g(n) = sqrt(n)^sqrt(n)，g(n) = O(2^n)的复杂度是多少？

Question

如果 g(n) = sqrt(n)^sqrt(n)，g(n) = O(2ⁿ) 的复杂度是多少？

感谢任何帮助。

Answer 1

比较两个指数函数时，一个有用的技巧是让它们具有相同的基数:

√n^√n = (2^{lg √n})^√n = 2^{√n lg √n}

现在你正在比较 2^{√n lg √n} 和 2ⁿ，希望从中很容易看出前一个函数的增长速度不如后者，所以 √n^√n = O(2ⁿ) 确实成立。