O(n2)
O(8n2)
O(nlog2n)
O(n)
多层嵌套采用的是乘法原则,即嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。对于此题,O(n)=T1(n) * T2(n),其中T2(n)即是第二层的时间的复杂度,对其单独分析的时间复杂度是 n;第一层我们重点分析一下:
将for(k=1; k<2n; k*=2) 转换为 while(k < 2n) k = k*2,这种形式应该见过吧,不就是等比数列嘛,通过对 2^x = n 求解可知 x = log2n,即是 T1(n) = log2n。
所以 O(n)=T1(n) * T2(n) = n * log2n。
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题