如果g(n)= sqrt(n)^ sqrt(n)，则g(n)的复杂度是否等于O(2 ^ n)?

本文介绍了如果g(n)= sqrt(n)^ sqrt(n)，则g(n)的复杂度是否等于O(2 ^ n)?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

如果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(2n)?

感谢您的帮助.

推荐答案

比较两个指数函数的一种有用技术是使它们具有相同的底数:

A useful technique when comparing two exponential functions is to get them to have the same base:

√ n √ n =(2 lg√ n )√ n = 2 √ n lg √ n

√n√n = (2lg √n)√n = 2√n lg √n

现在您正在将2 √ n lg√ n 与2 n 进行比较，希望由此可以很容易地看出前一个函数不会随着与后者一样迅速，因此√ n √ n = O(2 n )确实是正确的.

Now you're comparing 2√n lg √n against 2n, and hopefully from that it's easy to see that the former function does not grow as rapidly as the latter, so √n√n = O(2n) is indeed true.