0
A
回答
0
为什么你必须在这里使用主定理?它可以直接解决这样的:
T(n) = T(n-1) + n^3
T(n-1) = T(n-2) + (n-1)^3
T(n-2) = T(n-3) + (n-2)^3
. . .
. . .
. . .
T(1) = T(0) + 1^3
----------------------- (Add them all and cancel)
T(n) = T(0) + (n(n-1)/2)^2 (Sum of the cubes of the first n numbers)
因此,这是O(n^4)
0
T(n) = T(n-1) + n^3
= T(n-2) + n^3 + (n-1)^3
= T(n-i+1) + (n-i)^3 + ... + (n-1)^3 + n^3
= 1^3 + 2^3 + ... + (n/2)^3 + (n/2+1)^3 + ... + (n-1)^3
Throw bottom half and decrease the half top to n/2
> ((n/2)^3)*(n/2)
Ω(n^4)
Increase all to (n-1)
= 1^3 + 2^3 + ... + (n/2)^3 + (n/2+1)^3 + ... + (n-1)^3 < (n-1)^3*n = O(n^4)
T(n) = θ(n^4)
+0
好的解决方法谢谢,有没有办法直接计算1^3 + 3^3 + ... +(n + 2)^ 3? – flower
相关问题
- 1. 分而治之和递归
- 2. 递归背包(分而治之)
- 3. 分而治之算法
- 4. 分而治之算法
- 5. 分而治之算法
- 6. 分而治之的方法来计算根
- 7. 递归,分而治之算法,用于最长的非减少数字数组
- 8. Python:分而治之递归矩阵乘法
- 9. 学习分而治之算法
- 10. 分而治之算法的并行性
- 11. 分而治之:IndexSearch
- 12. 如何高效并行化分而治之算法?
- 13. 乘以分而治之
- 14. 分而治之JAVA向量
- 15. 分而治之 - 比较
- 16. Max Sum Subarray - 分而治之
- 17. 分而治之法peakFinder
- 18. 设计一个可以确定缺失整数的分而治之算法
- 19. 如何在C#中使用多线程实现分而治之算法?
- 20. 如何使用分而治之算法在y轴上找到最佳线条?
- 21. 如何使用“分而治之”方法对事件进行计数
- 22. 如何使用Master定理来描述递归?
- 23. 算法:分而治之(应用快速排序?!)
- 24. 分而治之算法(应用二进制搜索?!)
- 25. 递归计算保龄球得分
- 26. 使用递归计算上下数字
- 27. 中间点而治之算法实现
- 28. 如何计算递归函数的值?
- 29. 如何计算递归函数?
- 30. 如何递归计算的SQLite
聪明的想法。 – flower
好吧,我明白了,但这样计算太复杂,谢谢你的回答。我提出了你的答案,但由于我的名声不到15,它还没有显示出来。 – flower
但就是这样。看看这个(https://brilliant.org/wiki/sum-of-n-n2-or-n3/)。解决“尝试自己”的挑战,那么你将获得更多关于如何解决序列的知识。 – Miraj50