yzza123 2017-07-28 15:31 采纳率: 0%
浏览 1822

递归算法的时间复杂度

T(m,n) = T(m-1,n) + T(m,n-1)

对于这样一个递归算法,其时间复杂度是多少呀?

问题背景:

在一个正方网格中,只能沿着网格往上走或者往右走,求原点到指定坐标中有多少条路径。

为此设置一个递归函数,当指定坐标(m,n)中的m==0或者n==0时,函数值为1.

除此之外的场合,等于其(m-1,n)和(m,n-1)路径之和。

于是有T(m,n) = T(m-1,n) + T(m,n-1)递归算法。但是时间复杂度实在不会算,看了很多方法,但不知道用什么方法算。。。

附:附:有人说是O[ (m+n) ^2 ],我自己算是O[2 ^ (m+n) ]我的求解过程如图片所写...不知道正误...
请教!
图片说明

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-07-29 13:46
    关注

    如果是没有回路的,树,那么可以按照你的图算,是O(2^N)
    如果是正方形网格的不重复遍历,也就是有回路的图,那么就是O(N^2)

    评论

报告相同问题?

悬赏问题

  • ¥15 drone 推送镜像时候 purge: true 推送完毕后没有删除对应的镜像,手动拷贝到服务器执行结果正确在样才能让指令自动执行成功删除对应镜像,如何解决?
  • ¥15 求daily translation(DT)偏差订正方法的代码
  • ¥15 js调用html页面需要隐藏某个按钮
  • ¥15 ads仿真结果在圆图上是怎么读数的
  • ¥20 Cotex M3的调试和程序执行方式是什么样的?
  • ¥20 java项目连接sqlserver时报ssl相关错误
  • ¥15 一道python难题3
  • ¥15 牛顿斯科特系数表表示
  • ¥15 arduino 步进电机
  • ¥20 程序进入HardFault_Handler