永发信息网

求解算法时间复杂度的题 求完整解题步骤思路 30分

答案:2  悬赏:0  手机版
解决时间 2021-12-26 15:12
求解算法时间复杂度的题 求完整解题步骤思路 30分
最佳答案
如果就按这个递归式子算,计算第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)的常数做法,我个人没有想到,也许在数据规模小的情况下可以使用查表法做到.
全部回答
这个问题的回答的对
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
盖州青石岭供电营业厅地址有知道的么?有点事
个人简历:(从初中填起) 求范文~
单选题哲学是关于世界观的学说,哲学是A.人们
盖州榜式堡供电营业厅地址在哪?我要去那里办
单选题除去NaCl溶液中混有的少量Na2CO3得到较
同学日文怎么写
手心蜕皮痒是怎么回事
你是我的最爱无人能代替是哪首歌
盖州太阳升供电营业厅位置在什么地方啊,我要
锄组词有哪些两个字
想制作一个饭店的微信公众号,但是不知道微信
盖州九垄地供电营业厅办公地址在什么地方?我
请以“那一刻,我心飞扬”为题写一篇文章。要
星网数码上TXD,RXD的灯不亮怎么办啊
你认为最具有世界影响力的美国财经人是谁?
推荐资讯
解答题2010年大蒜、绿豆、叶菜、玉米等农产品
读某城市2003与2005年城市建设用地结构图,其
请问男女交往女方喜欢天天腻在一起...男方却
饿了么账户异常不能使用首减红包怎么办
高青县安全生产监督管理局在什么地方啊,我要
东郑村委会位置在什么地方啊,我要过去办理业
只欠东风是什么风
判断题对人体健康来说,科学有效的运动方式之
一个水果店进苹果200千克,购进的香蕉是苹果重
最新一期papi酱讲的是什么电影
为什么这套配置打lol会卡,开高特效在泉水里
家有喜事1997里是谁演员表
正方形一边上任一点到这个正方形两条对角线的
阴历怎么看 ?