求解算法时间复杂度的题 求完整解题步骤思路 30分
答案:2 悬赏:0 手机版
解决时间 2021-12-26 15:12
- 提问者网友：别再叽里呱啦
- 2021-12-25 22:12
求解算法时间复杂度的题 求完整解题步骤思路 30分
最佳答案
- 五星知识达人网友：孤独入客枕
- 2021-12-25 23:42
如果就按这个递归式子算,计算第n项需要的计算量An = ΣAi {i,0 -> n-1} 因此An = S(n-1) => An = 2*A(n-1) 又因为0,1两项可以直接算得. 故 A0 = 1, A1 = 1 所以第n项的计算量为{n=0 : 1, n>0 : 2^(n-1)} 总的来说是O(2^n)级别 当然真正实现这个算法的时候不会这么采用暴力的计算.如果加入记忆化,把每个Ti的值先记下,则时间复杂度可以降到O(n^2)级别 进一步优化,可以尝试计算这个递归数列的通项.不过我简单试了下发现最后要计算1/n的和,这个据我所知只能直接计算.这样整个算法的复杂度可以降到O(n). 至于楼下说的O(1)的常数做法,我个人没有想到,也许在数据规模小的情况下可以使用查表法做到.
全部回答
- 1楼网友：青尢
- 2021-12-26 00:24
这个问题的回答的对
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息
大家都在看
推荐资讯