首页 > 编程语言 >「笔记」递归算法复杂度分析

「笔记」递归算法复杂度分析

时间:2024-06-10 16:33:15浏览次数:24  
标签:log 递归 epsilon 复杂度 算法 Theta cases 定理

目录

写在前面

可恶的算法分析与设计!!!

递归算法形式

对于一个输入规模为 \(n\) 的递归算法,每次均为将整个问题划分为 \(a\) 个规模为 \(\frac{n}{b}\) 的子问题,回溯时将所有子问题合并需要 \(f(n)\) 的时间,定义函数 \(T(n)\) 代表该递归算法所需时间,则有递推式:

\[\forall n>b,\ T(n) = aT\left(\frac{T}{b}\right) + f(n) \]

递归树大力求和

根据递推式画出递归树。对于上述递归式其递归树形如:

  1. 根节点代表规模为 \(n\) 的原问题。
  2. 对于规模为 \(x\) 的节点,其子节点数为 \(a\),代表该问题分治后的所有规模为 \(\frac{x}{b}\) 的子问题。
  3. 对于规模为 \(x\) 的问题对应的子节点,节点上的值为 \(f(x)\)。
  4. 每层的右侧标出当前层中所有节点的和。

对递归树逐层右侧的值求和求和即得 \(T(n)\) 的值。

一个实例:

图片来源:https://blog.csdn.net/ypxcan/article/details/120452530

主定理 Master Theorem

对于上述函数 \(T(n)\),有:

\[\forall n>b,\ T(n) = aT\left(\frac{T}{b}\right) + f(n) \]

\[T(n) = \begin{cases} \Theta(n^{\log_b a}) &\exists \epsilon > 0, f(n) = O(n^{\log_b (a) - \epsilon}) &(1)\\ \Theta (f(n)) &\exists \epsilon\ge 0, f(n) = \Omega(n^{\log_b (a) + \epsilon}) &(2)\\ \Theta(n^{\log_b a} \log^{k + 1} n) &\exists k\ge 0, f(n) = \Theta(n^{\log_b a}\log^k n) &(3) \end{cases}\]

特别地,情况(2)中还需满足存在常数 \(c<1\),当 \(n\rightarrow +\infin\) 时 \(af\left(\frac{n}{b}\right)\le cf(n)\) 恒成立。

证明即考虑将上述时间含义的递归树并逐层求和,上述公式中莫名奇妙的 \(n^{\log_b a}\) 实际上即为递归树最底层的所需时间为 \(\Theta(1)\) 的子问题数量。具体证明过程详见 OI-wiki

根据证明过程可以得到上述三种情况分别代表的实际情况:

  • (1)瓶颈在于处理所有叶节点所需时间 \(\Theta(1)\times O(n^{\log_b a})\)。
  • (2)瓶颈在于分割与合并过程 \(f(n)\)。
  • (3)分割与合并过程与处理所有叶节点所需时间同级,上述额外限制 \(af\left(\frac{n}{b}\right)\le cf(n)\) 即限制了原问题分割后子问题的增长速率不会超过其本身。

典题

大部分情况下可以直接套主定理秒了,如果套不上公式只能大力求和。

1

\[T(n) = \begin{cases} 1 &(n = 1)\\ 2T\left(\frac{n}{2}\right) + 1 &(n>1) \end{cases}\]

有 \(a = 2, b = 2, \log_b a = \log_2 2 = 1\)。当取 \(\epsilon \in (0, 1]\) 时,有 \(f(n) = O(n^{\log_b (a) - \epsilon}) = O(n^{1 - \epsilon})\),则由主定理(1)有:

\[T(n) = \Theta(n^{\log_b a}) = \Theta(n) \]

2

\[T(n) = \begin{cases} 1 &(n = 1)\\ T\left(\frac{n}{2}\right) + n &(n>1) \end{cases}\]

有 \(a = 1, b = 2, \log_b a = \log_2 1 = 0\)。当取 \(\epsilon \in (0, 1]\) 时,有 \(f(n) = \Omega(n^{\log_b (a) + \epsilon}) = O(n^{\epsilon})\),则由主定理(2)有:

\[T(n) = \Theta(f(n)) = \Theta(n) \]

3

\[T(n) = \begin{cases} 1 &(n = 1)\\ 2T\left(\frac{n}{2}\right) + n &(n>1) \end{cases}\]

即为归并排序的复杂度。递归树见上述图片实例。

有 \(a = 2, b = 2, \log_b a = \log_2 2 = 1\)。当取 \(k = 0\) 时,有 \(f(n) = \Theta(n^{\log_b a}\log^k n) = \Theta(n)\),则由主定理(3)有:

\[T(n) = \Theta(n^{\log_b a}\log^{k + 1} n) = \Theta(n\log n) \]

4

\[T(n) = \begin{cases} 1 &(n = 1)\\ 2T\left(\frac{n}{2}\right) + n\log n &(n>1) \end{cases}\]

CDQ 分治的复杂度。

有 \(a = 2, b = 2, \log_b a = \log_2 2 = 1\)。当取 \(k = 1\) 时,有 \(f(n) = \Theta(n^{\log_b a}\log^k n) = \Theta(n\log n)\),则由主定理(3)有:

\[T(n) = \Theta(n^{\log_b a}\log^{k + 1} n) = \Theta(n\log^2 n) \]

写在最后

奇怪的是网络上搜到的主定理的定义都是不完全的,比如以下参考中指出的那篇,在他们的定义下会出现明明可以适用主定理但是不存在于定义中的情况。为什么会有这种残疾版的定义?莫名奇妙!

要不是我现在妈的忙着傻逼期末我一定去溯源妈的傻逼期末

参考:

标签:log,递归,epsilon,复杂度,算法,Theta,cases,定理
From: https://www.cnblogs.com/luckyblock/p/18240783

相关文章

  • 社交网络算法改进的深度极限学习机DELM的分类
    社交网络算法改进的深度极限学习机DELM的分类文章目录社交网络算法改进的深度极限学习机DELM的分类1.ELM原理2.深度极限学习机(DELM)原理3.社交网络算法4.社交网络算法改进DELM5.实验结果6.参考文献7.Matlab代码1.ELM原理ELM基础原理请参考:https://blog.csdn.net/u01......
  • 骑手优化算法改进的深度极限学习机DELM的分类
    骑手优化算法改进的深度极限学习机DELM的分类文章目录骑手优化算法改进的深度极限学习机DELM的分类1.ELM原理2.深度极限学习机(DELM)原理3.骑手优化算法4.骑手优化算法改进DELM5.实验结果6.参考文献7.Matlab代码1.ELM原理ELM基础原理请参考:https://blog.csdn.net/u01......
  • 野马算法改进的深度极限学习机DELM的分类
    野马算法改进的深度极限学习机DELM的分类文章目录野马算法改进的深度极限学习机DELM的分类1.ELM原理2.深度极限学习机(DELM)原理3.野马算法4.野马算法改进DELM5.实验结果6.参考文献7.Matlab代码1.ELM原理ELM基础原理请参考:https://blog.csdn.net/u011835903/article/......
  • 卷尾猴算法改进的深度极限学习机DELM的分类
    卷尾猴算法改进的深度极限学习机DELM的分类文章目录卷尾猴算法改进的深度极限学习机DELM的分类1.ELM原理2.深度极限学习机(DELM)原理3.卷尾猴算法4.卷尾猴算法改进DELM5.实验结果6.参考文献7.Matlab代码1.ELM原理ELM基础原理请参考:https://blog.csdn.net/u011835903/......
  • 嵌入式浅谈之“梯形”加减速MCU算法实现
    书接上回,上章我们讲到原理,本章我们来聊聊实现。在笔者的实际项目经历中,梯形加减速运用的比较广泛,主要以其优秀的加减速能力、对算法实现资源的需求较小、实现难度适中而被广泛应用。下面就简单介绍一下基于MCU的算法实现过程,以STM32为例。采用“梯形”加减速算法,在运动过......
  • 初始C语言——结构化算法的结构
    C语言程序是一种程序化程序,也就是说,可以用C语言程序来解决的问题,都可以分解成相互独立的几个部分,每个部分都可以通过简单的语句或结构来实现。一般而言,对于结构化的程序,一个完整的算法可以用“顺序结构”,“分支结构”和“循环结构”的有机组合来表示。(一)----------顺序结构......
  • 算法金 | AI 基石,无处不在的朴素贝叶斯算法
    大侠幸会,在下全网同名「算法金」0基础转AI上岸,多个算法赛Top「日更万日,让更多人享受智能乐趣」历史上,许多杰出人才在他们有生之年默默无闻,却在逝世后被人们广泛追忆和崇拜。18世纪的数学家托马斯·贝叶斯(ThomasBayes)便是这样一位人物贝叶斯的研究,初看似平凡,其人亦......
  • 优雅的快排之分治与递归思想,透彻理解快排
    摘要:给你一个数组,要求你对其按照从小到大的顺序进行排序.你是怎么做的呢?英国计算机科学家东尼.霍尔在英国国家物理实验室工作的时候提出一种名为快速排序的排序算法,它可以高效地将一个数组进行快速排序.那么霍尔是怎么想到的?接下来根据从y总那里学到的以及个人的理解来介......
  • 如何应对缺失值带来的分布变化?探索填充缺失值的最佳插补算法
    本文将探讨了缺失值插补的不同方法,并比较了它们在复原数据真实分布方面的效果,处理插补是一个不确定性的问题,尤其是在样本量较小或数据复杂性高时的挑战,应选择能够适应数据分布变化并准确插补缺失值的方法。我们假设存在一个潜在的分布P,从中得出观察值X。此外,还绘制了一个与X相同......
  • GWO-LSTM多输入回归预测|灰狼算法-双向长短期神经网络|Matlab
    目录一、程序及算法内容介绍:基本内容:亮点与优势: 二、实际运行效果:三、算法介绍:四、完整程序下载:一、程序及算法内容介绍:基本内容:本代码基于Matlab平台编译,将GWO(灰狼群算法)与Bi-LSTM(双向长短期记忆神经网络)结合,进行多输入数据回归预测输入训练的数据包含7个特......