0 math big-o time-complexity big-theta
有人告诉过我
1 + 8 + 27 + 64 + ... +(√n)3 =Θ(n 2)
为什么会这样？
为了确保我明白你在说什么,你很好奇为什么总和
1 3 + 2 3 + 3 3 + ... +(√n)3 =Θ(n 2)
一种方法是查找前m个立方体之和的公式.这等于
(m(m + 1)/ 2)2
所以让我们插入m =√n,这给出了
1 3 + 2 3 + 3 3 + ... +(√n)3
=((√n)((√n)+ 1)/ 2)2
=((n +√n)/ 2)2
=(n 2 +2n√n+ n)/ 4
最后的表达式给出了第一个√n完美立方体之和的精确值.注意,该表达式是Θ(n 2),因为n 2是主导项.
希望这可以帮助!