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

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

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

        分治法的道理非常简单,就是把一个大的复杂的问题分为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)。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏利炳根的专栏

学习笔记DL003:神经网络第二、三次浪潮,数据量、模型规模,精度、复杂度,对现实世界冲击

神经科学,依靠单一深度学习算法解决不同任务。视觉信号传送到听觉区域,大脑听学习处理区域学会“看” (Von Melchner et al., 2000) 。

40000
来自专栏小小挖掘机

如何买卖股票?不要慌,我有妙招!

Leetcode第121题到123题连续出现了三道买卖股票相关的题目,一年前的网易笔试和半年前的百度面试都遇到过121题,不过不用慌,看完本文,你一定能够完美解...

29890
来自专栏深度学习自然语言处理

【干货】基于注意力机制的seq2seq网络

seq2seq seq2seq的用途有很多,比如机器翻译,写诗,作曲,看图写文字等等用途很广泛!该模型最早在2014年被Cho和Sutskever先后提出,前者...

48560
来自专栏语言、知识与人工智能

游戏文本关键词提取工作的尝试和探索

如何将合适的游戏文本打上正确的关键词标签,并将内容推送给恰当的用户成为一个重要的课题。

1.6K50
来自专栏AI科技评论

ACL论文 | 深度学习大神新作,神经网络的自然语言翻译应用

在 8月7日在德国柏林召开的2016 计算语言学(ACL)大会上,学者Thang Luong、Kyunghyun Cho 和 Christopher D. Ma...

37450
来自专栏小石不识月

如何为神经机器翻译配置一个编码器 - 解码器模型

循环神经网络(RNN,Recurrent Neural Networks)中的编码器 - 解码器(Encoder-Decoder)架构在标准机器翻译基准上取得了...

38690
来自专栏深度学习自然语言处理

pyTorch基础入门练习

import导入 import torch#基本的torch函数 import torch.autograd as autograd#自动求导 import t...

416100
来自专栏人工智能LeadAI

机器学习实战 | 数据探索(变量变换、生成)

1.1、什么是变量变换? 在数据建模中,变换是指通过函数替换变量。 例如,通过平方/立方根或对数x替换变量x是一个变换。 换句话说,变换是一个改变变量与其他变量...

43160
来自专栏数值分析与有限元编程

有限元 | 经典梁单元刚度矩阵推导

经典欧拉梁单元不考虑剪切变形。基于试函数的能量方法(也称为泛函极值方法),基本要点是不需求解原微分方程,但需要假设一个满足位移边界条件的许可位移场。因此,如何寻...

52270
来自专栏懒人开发

(4.9)James Stewart Calculus 5th Edition:Newton’s Method

Newton’s Method 牛顿法则, 又叫 Newton-Raphson method 牛顿迭代法则

13040

扫码关注云+社区

领取腾讯云代金券