算法设计与分析复习01：主方法求递归算法时间复杂度

悠悠 2024-03-30 13:32 49阅读 0赞

> 作者：非妃是公主  
> 专栏：《算法》  
> **个性签：顺境不惰，逆境不馁，以心制境，万事可成。——曾国藩**
> 
> ![在这里插入图片描述][7cea80270e124c7faeb5f6b5fd8ac41a.jpeg]
> 
> ### 专栏系列文章 ###
> 
> [算法设计与分析复习01：主方法求递归算法时间复杂度][01]
> 
> [算法设计与分析复习02：分而治之算法][02]
> 
> [算法设计与分析复习03：动态规划算法][03]  
> [算法设计与分析复习04：贪心算法][04]
> 
> [算法设计与分析复习05：回溯及分支限界][05]
> 
> [算法设计与分析复习06：随机化算法][06]
> 
> [算法设计与分析复习07：样题][07]
> 
> #### 文章目录 ####
> 
>  *   *  专栏系列文章
>      *  复习重点
>      *  算法复杂度分析——主方法
>      *   *  例题1：
>          *  例题2：
>          *  例题3：

### 复习重点 ###

![在这里插入图片描述][16ee73d314d24fd7a218b4b65604a9f6.png]

### 算法复杂度分析——主方法 ###

T ( n ) = a T ( n b ) + f ( n ) T(n)=aT(\\frac\{n\}\{b\})+f(n) T(n)=aT(bn)\+f(n)

*  其中 `a≥1` 和 `b>1` 是常数， `f(n)` 是渐进函数 。
 *  上述递归式描述的是这样一种算法的运行时间：
    
     *  它将规模为 `n` 的问题分解为 `a` 个子问题 每个子问题规模为  n b \\frac\{n\}\{b\} bn ，其中 `a` 和 `b` 都是正常数。
     *  a 个子问题递归地进行求解，每个花费时间 T(n/b) 。
     *  函数 f(n) 包含了问题分解和子问题解合并的代价 。
     *  其中  n b \\frac\{n\}\{b\} bn 指  n b \\frac\{n\}\{b\} bn 的上取整或者是下取整，对结果不会造成影响。

![在这里插入图片描述][74cf86e6414a4e97841de98c94b5ef51.png]

![在这里插入图片描述][19664d4bc1f946e9af2dd7c456c95726.png]

#### 例题1： ####

![46bad5fe0b7c467abaf086fb4e935422.png][]

#### 例题2： ####

![在这里插入图片描述][42d7c7e057ce433ebe3be90f6eccffc2.png]

#### 例题3： ####

![在这里插入图片描述][68409e4610114302b657ad368a188ecf.png]

[7cea80270e124c7faeb5f6b5fd8ac41a.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e7fd8f819b1a47db92081a902d979215.jpeg
[01]: https://blog.csdn.net/myf_666/article/details/128509102
[02]: https://blog.csdn.net/myf_666/article/details/128509126
[03]: https://blog.csdn.net/myf_666/article/details/128509143
[04]: https://blog.csdn.net/myf_666/article/details/128509159
[05]: https://blog.csdn.net/myf_666/article/details/128509168
[06]: https://blog.csdn.net/myf_666/article/details/128509174
[07]: https://blog.csdn.net/myf_666/article/details/128509183
[16ee73d314d24fd7a218b4b65604a9f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/fc1fb01e181e4b2fb74d19f3658c2006.png
[74cf86e6414a4e97841de98c94b5ef51.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9d8a17ed71e14ef092e86d4bc1dbef1d.png
[19664d4bc1f946e9af2dd7c456c95726.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/10e6ffff2a794dc586a3c6eb682216a1.png
[46bad5fe0b7c467abaf086fb4e935422.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/06e95d648be547f8b24136257e30fdab.png
[42d7c7e057ce433ebe3be90f6eccffc2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/5b0d8efce5164229bb12f4c8daa49c1e.png
[68409e4610114302b657ad368a188ecf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/ba8ae335a49c492bbe5e03ebca4a4e95.png