我被告知
1 + 8 + 27 + 64 + ... + (√n) 3 = Θ(n 2 )
为什么会这样？
问问题
168 次
1 回答
8
为了确保我理解你在说什么，你很好奇为什么总和
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是主导项。
希望这可以帮助！
于 2013-05-04T17:50:32.900 回答