如果g(n)= sqrt(n)^ sqrt(n),g(n)的复杂度是否为O(2 ^ n)？
joh*_*and 6 algorithm big-o discrete-mathematics
如果g(n)= sqrt(n)sqrt(n),g(n)的复杂度是否为O(2 n)？
任何帮助表示赞赏.
比较两个指数函数时的一个有用技巧是让它们具有相同的基数:
√N √N =(2 LG√N)√N = 2 √NLG√N
现在你比较2√nggn和2 n,希望从中可以很容易地看出前一个函数的增长速度不如后者那么快,所以√n√n = O(2 n)确实是真的.
- 如果不清楚第一个相等是由于'2 ^ lg(n)= n`,其中_lg_是对数为2的对数.第二个是由于指数的幂律,通常你有`(b ^ n)^ m = b ^(n*m)`. (2认同)
其他证明很短且很好,但是这里有更详细的证据可以解释大哦符号的定义和所需限制的计算.
一个函数g(n)由另一个函数上限f(n)由大哦符号(g(n) = O(f(n)))如果它拥有(源)
放入功能,我们必须计算
首先对这个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),我们可以将其简化为:
此限制确实为零,因为平方根通过常用函数的订单增长快于对数.因此,较低函数的指数增长得比较高函数的指数增长得快.因此g(n) = O(2^n),第一定理得到了严格的证明.