递归算法时间复杂度题目求解答....
T(n)=(1/n)(T(0)+T(1)+....+T(n-1))+5n求时间复杂度是多少求详细解答..谢谢...
T(n) =(1/n) (T(0) + T(1) + .... + T(n - 1)) + 5n 求 时间复杂度是多少 求详细解答..谢谢
展开
展开全部
如果就按这个递归式子算,计算第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)的常数做法,我个人没有想到,也许在数据规模小的情况下可以使用查表法做到.
因此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)的常数做法,我个人没有想到,也许在数据规模小的情况下可以使用查表法做到.
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
Sievers分析仪
2024-10-13 广告
是的。传统上，对于符合要求的内毒素检测，最终用户必须从标准内毒素库存瓶中构建至少一式两份三点标准曲线；必须有重复的阴性控制；每个样品和PPC必须一式两份。有了Sievers Eclipse内毒素检测仪，这些步骤可以通过使用预嵌入的内毒素标准...
点击进入详情页
本回答由Sievers分析仪提供
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
