专栏首页swag codeMaster Method Restated-主项定理-递归时间复杂度

Master Method Restated-主项定理-递归时间复杂度

对于一个递归实现的分治算法,其时间复杂度表示为:

T(n) = aT(n/b)+h(n)

T(N)=aT(n/b)+O(N^d)

b是规模 a是调用次数

其中,a>=1; b>1; h(n)是不参与递归部分的时间复杂度。

比较n^log b (a)与Θ(h(n)) 的大小(Θ的含义和“等于”类似,而大O的含义和“小于等于”类似,感觉好像这里都可以用):

n^log b (a)= Θ(h(n)) :该方法的复杂度为  Θ(h(n)*log(n))

n^log b (a)< Θ(h(n)) :该方法的复杂度为  Θ(h(n))

n^log b (a)> Θ(h(n)) :该方法的复杂度为  Θ(n^log b (a))

例如:

T(n) = T(n/2)+1:Θ(log(n))(二分查找) T(n) = 2T(n/2)+n :Θ(n*log(n))(归并排序)

以上都属于“等于”的情况。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java中的private、protected、public和default的区别(详解)

    (1)对于public修饰符,它具有最大的访问权限,可以访问任何一个在CLASSPATH下的类、接口、异常等。它往往用于对外的情况,也就是对象或类对外的一种接口...

    sr
  • Tomcat服务器配置Https协议

    修改Tomcat配置文件: 打开Tomcat安装目录/conf/server.xml,修改如下配置,并取消注释 注:这里以Tomcat8.0为例,8.5以上配...

    sr
  • 常用算法排序-时间空间复杂度表

    sr
  • Android APP测试的日志文件抓取

      实时打印的主要有:logcat main,logcat radio,logcat events,tcpdump,还有高通平台的还会有QXDM日志

    流柯
  • Linux日志管理

    要知道的是,我们的 Linux 主机在背景之下有相当多的 daemons 同时在工作着,这些工作中的程序总是会显示一些讯息,这些显示的讯息最终会被记载到登录文件...

    小柒吃地瓜
  • Mysql日志解析

    修改Mysql配置 Mysql配置地址为: C:\Program Files (x86)\MySQL\MySQL Server 5.5 如果无法修改可以把my....

    用户1154259
  • Nginx日志配置

    众所周知,线上如果出现事故我们通常都是查看日志去进行问题定位并且进行修复。使用好Nginx日志有利于我们线上进行修复异常问题。在Nginx中日志主要分为两种:...

    逆月翎
  • 【kafka】高吞吐源码分析-顺序写入与刷盘机制

    kafka作为一个处理实时数据和日志的管道,每秒可以处理几十万条消息。其瓶颈自然也在I/O层面,所以其高吞吐背后离不开如下几个特性:

    皮皮熊
  • PHP线程安全与非线程安全的区别(NTS/TS)选择?

    很多时候,我们在做PHP环境配置的时候,很多人都是直接去乱下载PHP版本的,但是他不清楚:从2000年10月20日发布的第一个Windows版的PHP3.0.1...

    周俊辉
  • 原 mysql开启日志记录

    用户1220053

扫码关注云+社区

领取腾讯云代金券