这个表达式的时间复杂度怎么求

来源：百度知道 编辑：UC知道 时间：2024/06/23 12:15:50
怎么求这个表达式的时间复杂度 书上写的复杂度是 Θ(n)
for(j=0,j <n,j*=2)
for(k=0,k <j,k++)
x++;

我只能推出Θ(nlogn)
写错了 j k 的初始值都为1
for(j=1,j <n,j*=2)
for(k=1,k <j,k++)
x++;

额……好晕，第二个for循环就不会循环了，第一个又是无限循环，j永远等于0
成死循环了……这个复杂度是不是很大了……无穷？

再接一段，哈哈……
第一个for循环的复杂度应该是logn，第二个大概是2^0-1+2^1-1+2^2-1+……+2^logn-1然后两个相乘……，应该还有一个logn取整的问题……晕了
对不对我就不晓得了……算得很晕了，你可以尝试编个小程序算一下，哈哈