一道时间复杂度的题,等待各位大佬解答。(不要ai)

00cac3510e18fcf0683b630f44f2b06
各位请作答!!!

1 Like

不会,楼下解答

不会,楼下作答

image

1 Like

以为数学题我兴冲冲的跑了过来

不会 楼下解答

1 Like

问问天才少女砂糖酱

1 Like

也算是数学题

好吧我贴万能解答了
image
还正好是ijk

直觉是
image

三层嵌套是三个因子乘在一起, 外面是二分增加的, 所以是log n
里面两层是+1累加的, 所以复杂度就是n,
结果是n乘n乘log(n)

1 Like

image

1 Like

推了一下应该就是n²,等比数列求和

内层去掉常数也是log n,所以是log n的立方

1 Like

O(n^2)

\sum_{i=1}^{[\log_2^n]}(2^i)^2 = \sum_{i=1}^{[\log_2^n]}4^i = \dfrac{4^{[\log_2^n]+1} - 1}{4-1} \approx \dfrac {4n^2 - 1}{3}

感觉这个结果好怪,有点反直觉,不知道对不对

4 Likes

不得不求助计算器了
image

1 Like

等比数列求和,合理 跟我算的一样

答案真是五花八门啊

不管,3个循环就是n**3!

错误解答,警示后人 :tieba_087::
设最外层循环了N次,有
\left\lceil\log_{2}n\right\rceil = N

O[f(n)]=O[\frac{1}{2}(1+2^2+3^2\cdots+N^2)+\frac{1}{2}(1+2+3\cdots+N)]
=O(N^3)
=O(log_2^3 n)

正确解答:
O[f(n)]=O[(1+2^2+(2^2)^2\cdots+2^{2N})]
=O(2^{2N}-1)
=O(n^2)

1 Like

这么多,谁的回答是对的呢? :tieba_087: