一道时间复杂度的题，等待各位大佬解答。（不要ai）

[rookis2 (我无名)]

难为人啊

[Neon]

跑了一下代码，是O(n^2)

内两层运行次数是1+2+3+…+(2^i-1)，外层是1…Log2(n)，所以

[Ferrari (F1)]

我选择相信人，gpt每次回答都不一样

[ninijia]

之前傻逼了 把加法当成乘法了 这回应该是对的 注意大O表示法的话 只保留次数最大的 把项写出来再用等比数列求和 再根据前面各位大佬的分析 基本可以确定就是O(n^2) 我这里只是把详细过程写了一下

[AlbertEinstein (阿尔伯特·爱因斯坦)]

这么多不同答案，楼主又迷茫了，到底信谁呢

[ninijia]

看着谁合理信谁

[Camreishi]

老哥，你这里写的意思是这两部分相等吗？好像不太对吧

[Camreishi]

\frac{i(i+1)}{2}
直接拆开用平方和公式

[ninijia]

额 哪里不对咧

[Camreishi]

比如看第4项
左边=\frac{5*6}{2}
右边=2^2(2^3+1)

[ninijia]

嗷嗷 这里i是每次乘2一直到n 不是每次加1 所以下一项其实是8*9/2 不是5*6/2 因此其实也不能直接用平方和公式 不过从大O的角度来说最后应该都是 n^2 的复杂度

[Camreishi]

嗷，我想错了

[ninijia]

哈哈 问题不大 虽然中间有点小误差 不影响最终结果