Unit1_1:分治问题之时间复杂度求解

2023-10-30 14:04

本文主要是介绍Unit1_1:分治问题之时间复杂度求解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 背景
  • 递归树法
    • 案例一
    • 案例二
    • 局限性
  • 代入法/替代法
  • 主方法(重点)

背景

当碰到形如 T ( n ) = a T ( ⌈ n b ⌉ ) + O ( n d ) T(n)=aT(\lceil \frac{n}{b} \rceil)+O(n^d) T(n)=aT(⌈bn⌉)+O(nd)的递推式,本质上就是将问题转化为规模更小的子问题求解,此时有三种思路。

递归树法

案例一

T ( n ) = { 2 T ( n 2 ) + n i f n > 1 1 i f n = 1 T(n)=\left\{ \begin{array}{ll} 2T(\frac{n}{2})+n & if \space n>1 \\ 1 & if \space n=1 \nonumber \end{array} \right. T(n)={2T(2n)+n1if n>1if n=1
可以利用递归树:
在这里插入图片描述
画出树,高满足 2 h = n 2^h=n 2h=n,因此 h = l o g 2 n h=log_{2}n h=log2n,而叶子共有n个,因此总的时间复杂度 T ( n ) = n l o g n T(n)=nlogn T(n)=nlogn

案例二

T ( n ) = { 3 T ( n 4 ) + n 2 i f n > 1 1 i f n = 1 T(n)=\left\{ \begin{array}{ll} 3T(\frac{n}{4})+n^2 & if \space n>1 \\ 1 & if \space n=1 \nonumber \end{array} \right. T(n)={3T(4n)+n21if n>1if n=1
在这里插入图片描述
每层个数即 3 h 3^h 3h个。最后一层高度 h = l o g 4 n h=log_4n h=log4n,再利用对数技巧代入,即可求出叶子的个数,而时间复杂度为:
在这里插入图片描述
等比数列求解

局限性

T ( n ) = { T ( n 3 ) + T ( 2 n 3 ) + n i f n > 2 1 i f n = 1 , 2 T(n)=\left\{ \begin{array}{ll} T(\frac{n}{3})+ T(\frac{2n}{3})+n & if \space n>2 \\ 1 & if \space n=1,2 \nonumber \end{array} \right. T(n)={T(3n)+T(32n)+n1if n>2if n=1,2
在这里插入图片描述
此时树的高度不一致,无法计算

代入法/替代法

此法先假设时间复杂度,再去验证假设成立。因此最难之处在于怎么假设,用处不大

主方法(重点)

T ( n ) = a T ( ⌈ n b ⌉ ) + O ( n d ) T(n)=aT(\lceil \frac{n}{b} \rceil)+O(n^d) T(n)=aT(⌈bn⌉)+O(nd)的时间复杂度如下:

T ( n ) = { O ( n d ) d > log ⁡ b a O ( n d l o g n ) d = log ⁡ b a O ( n log ⁡ b a ) d < log ⁡ b a T(n)=\left\{ \begin{array}{ll} O(n^d) & d>\log_{b}a \\\\ O(n^{d}logn) & d=\log_{b}a \\\\ O(n^{\log_{b}a}) & d<\log_{b}a \nonumber \end{array} \right. T(n)= O(nd)O(ndlogn)O(nlogba)d>logbad=logbad<logba

以后碰到这种递推分治式子代入公式即可

这篇关于Unit1_1:分治问题之时间复杂度求解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/308425

相关文章

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五

从基础到进阶详解Pandas时间数据处理指南

《从基础到进阶详解Pandas时间数据处理指南》Pandas构建了完整的时间数据处理生态,核心由四个基础类构成,Timestamp,DatetimeIndex,Period和Timedelta,下面我... 目录1. 时间数据类型与基础操作1.1 核心时间对象体系1.2 时间数据生成技巧2. 时间索引与数据

MySQL 设置AUTO_INCREMENT 无效的问题解决

《MySQL设置AUTO_INCREMENT无效的问题解决》本文主要介绍了MySQL设置AUTO_INCREMENT无效的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参... 目录快速设置mysql的auto_increment参数一、修改 AUTO_INCREMENT 的值。

关于跨域无效的问题及解决(java后端方案)

《关于跨域无效的问题及解决(java后端方案)》:本文主要介绍关于跨域无效的问题及解决(java后端方案),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录通用后端跨域方法1、@CrossOrigin 注解2、springboot2.0 实现WebMvcConfig

Go语言中泄漏缓冲区的问题解决

《Go语言中泄漏缓冲区的问题解决》缓冲区是一种常见的数据结构,常被用于在不同的并发单元之间传递数据,然而,若缓冲区使用不当,就可能引发泄漏缓冲区问题,本文就来介绍一下问题的解决,感兴趣的可以了解一下... 目录引言泄漏缓冲区的基本概念代码示例:泄漏缓冲区的产生项目场景:Web 服务器中的请求缓冲场景描述代码

Java死锁问题解决方案及示例详解

《Java死锁问题解决方案及示例详解》死锁是指两个或多个线程因争夺资源而相互等待,导致所有线程都无法继续执行的一种状态,本文给大家详细介绍了Java死锁问题解决方案详解及实践样例,需要的朋友可以参考下... 目录1、简述死锁的四个必要条件:2、死锁示例代码3、如何检测死锁?3.1 使用 jstack3.2

解决JSONField、JsonProperty不生效的问题

《解决JSONField、JsonProperty不生效的问题》:本文主要介绍解决JSONField、JsonProperty不生效的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录jsONField、JsonProperty不生效javascript问题排查总结JSONField

github打不开的问题分析及解决

《github打不开的问题分析及解决》:本文主要介绍github打不开的问题分析及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、找到github.com域名解析的ip地址二、找到github.global.ssl.fastly.net网址解析的ip地址三

MySQL版本问题导致项目无法启动问题的解决方案

《MySQL版本问题导致项目无法启动问题的解决方案》本文记录了一次因MySQL版本不一致导致项目启动失败的经历,详细解析了连接错误的原因,并提供了两种解决方案:调整连接字符串禁用SSL或统一MySQL... 目录本地项目启动报错报错原因:解决方案第一个:第二种:容器启动mysql的坑两种修改时区的方法:本地

springboot加载不到nacos配置中心的配置问题处理

《springboot加载不到nacos配置中心的配置问题处理》:本文主要介绍springboot加载不到nacos配置中心的配置问题处理,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录springboot加载不到nacos配置中心的配置两种可能Spring Boot 版本Nacos