前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >分治法时间复杂度求解秘籍

分治法时间复杂度求解秘籍

作者头像
rainchxy
发布2018-09-13 16:11:37
3.4K0
发布2018-09-13 16:11:37
举报
文章被收录于专栏:趣学算法

分治法时间复杂度求解秘籍

本文来自快速入门算法书——《趣学算法》

        分治法的道理非常简单,就是把一个大的复杂的问题分为a(a>1)个形式相同的子问题,这些子问题的规模为n/b,如果分解或者合并的复杂度为f(n),那么总的时间复杂度可以表示为:

     那么如何求解时间复杂度呢?

  1. 递推求解法 我们上面的求解方式都是递推求解,写出其递推式,最后求出结果。 例如:合并排序算法的时间复杂度递推求解:
  1. 递归树求解法 递归树求解方式其实和递推求解一样,只是递归树更清楚直观的显示出来,更能够形象的表达每层分解的结点和每层产生的成本有多少。例如:

如图3-67所示。

图3-67 分治递归树

  1. 大师解法
  • 我们用递归树来说明大师解法:

如图3-68所示。

图3-68大师解法递归树

时间复杂度=叶子数*T(1)+成本和

时间复杂度=成本和。 现在我们只需要观察每层产生的成本的发展趋势,是递减的还是递增的,还是每层都一样?每层成本的公比为

  • 例如:
  • 画出递归树,观察每层产生的成本:

成本的公比小于1,时间复杂度按第1层计算;

成本的公比大于1,时间复杂度按最后1层计算;

成本的公比等于1,时间复杂度按第1层*树高计算;

大师解法:

递归树如图3-69所示。

图3-69 大师解法递归树

    首先从递归树中观察每层产生的成本发展趋势,每层的成本有时不是那么有规律,需要仔细验证才行。比如我们得到第3层是(5/16)2n2,需要验证第4层是(5/16)3n2,…。经过验证,我们发现每层成本是一个等比数列,公比为5/16<1,呈递减趋势,那么只需要计算第一项即可。时间复杂度:T(n) =O(n2)。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年01月03日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档