在前面的文章中,我们讨论了循环的时间复杂度分析。很多算法是具有递归性质的,当我们的分析的时候得到的是递推关系的时间复杂度。
例如,在归并排序中,对一个给定的数组进行排序,我们把它分成两半,并对这两半递归地重复这个过程。最后,我们合并结果。时间复杂度可以写成:
T(n) = 2T(n/2) + cn. 还有许多其他算法,如二分查找,汉诺塔等都可以递推公式。
主要有三种方式来递归公式。
1)替代法:我们做一个猜测的解,然后用数学归纳法证明的猜测是正确的或不正确的。
例如:T(n) = 2T(n/2) + n。 我们猜测解为:T(n) = O(nLogn).
现在用数学归纳法来证明我们的猜测。
需要证明 T(n) <= cn Logn. 我们可以假设对于值小于n时这个公式是成立的。
1 |
T(n) = 2T(n/2) + n |
2 |
<= cn/2Log(n/2) + n
|
3 |
= cnLogn - cnLog2 + n
|
4 |
= cnLogn - cn + n
|
5 |
<= cnLogn
|
2)递归树方法
在这个方法中,我们得出一个递归调用树,并计算树的每一层的时间。最后,我们对各层相加。要绘制递归树,我们从给定的递归出发,一直递推下去直到我们找到里面的模式。这个模式一般是典型的等差或等比级数。
例如对这个递归方程:T(n) = T(n/4) + T(n/2) + cn^2
1 |
cn2 (cn2 即为 cn^2)
|
2 |
/ \
|
3 |
T(n/4) T(n/2) |
如果我们进一步分解表达T(n / 4)和T(n / 2), 我们得到以下递归树。
01 |
cn2
|
02 |
/ \
|
03 |
c(n2)/16 c(n2)/4
|
04 |
/ \ / \
|
05 |
T(n/16) T(n/8) T(n/8) T(n/4)
|
06 |
(一直向下分解cn2)
|
07 |
/ \
|
08 |
c(n2)/16 c(n2)/4
|
09 |
/ \ / \
|
10 |
c(n2)/256 c(n2)/64 c(n2)/64 c(n2)/16 |
11 |
/ \ / \ / \ / \
|
要知道 T(n)的值,我们需要相加所有层的值。如果从最上面开始加,可以得到下面的式子:
T(n) = c(n^2 + 5(n^2)/16 + 25(n^2)/256) + ….
上述系列是几何级数为5/16。
为得到一个上限,我们求无穷级数的和: (n^2)/(1 – 5/16) 即为 O(n^2)
主定理
主定理是解决递归的一种直接方法。但仅用于一些类型或可以转换为以下类型的递归公式:
T(n) = aT(n/b) + f(n) (a >= 1 且 b > 1)
有以下三种情况:
如何计算?
主定理主要来自递归树方法。如果我们画T(n) 的递归树 T(n) = aT(n/b) + f(n),我们会发现 根节点的值为f(n) ,所有的叶子节点的和为 其中 c为 .
递归树的高度为:
在递归树的方法中,我们计算所有节点的和。如果在叶子节点的值是多项式的,那么叶子是占主导地位的一部分,而我们的结果变成叶子节点的值(情况1)。
如果叶和根是渐近一样的,那么结果就变成高度乘以在所有层的和(情况2)。如果根节点的值是渐近多,那么我们的结果变成在根的值(情况3)
一些时间复杂度可以使用主定理进行评估的例子
归并排序:为T(n) = 2T(n/2) + 。它属于在第二种情况, c为1并且 也1。因此该解决方案是
二分查找:T(n) = T(n/2) + . 。它也属于情况2. c是0并且也为0。因此该解决方案是
注:
1)主定理并不能用来解决所有形式为 T(n) = aT(n/b) + f(n) 的递归式,往往和给定的3种情况有第一定的差距。例如 T(n) = 2T(n/2) + n/Logn 不能用主定理解决。
2) 第二种情况可以扩展为 f(n) = . 如果 k >= 0 且 c = , 那么 T(n) =
参考:http://www.geeksforgeeks.org/analysis-algorithm-set-4-master-method-solving-recurrences/
参考视频地址:http://v.163.com/movie/2010/12/2/E/M6UTT5U0I_M6V2T4T2E.html
相关推荐
通过Python代码实现了前序、中序、后序遍历的递归算法,并分析了时间复杂度和空间复杂度的计算方式。最后,文章还讨论了使用栈来实现树遍历的方法,并对递归思想的理解进行了深入分析。 知识点一:树的基础知识 树...
在算法分析中,空间复杂度是指执行一个算法所需内存空间的度量。当提到空间复杂度为O(1)时,意味着无论输入规模多大,算法所需的额外存储空间都是常数,不会随着问题规模的增加而增长。这是一种理想的情况,通常在...
本文主要探讨了Java中几种常见的排序算法(冒泡排序、选择排序、插入排序、希尔排序)以及递归算法的时间复杂度分析。通过具体代码示例和理论分析,帮助读者理解不同排序算法的特点及其在实际应用中的性能表现。 ##...
- 主定理是分析递归算法时间复杂度的一种强大工具,尤其适用于形如`T(n) = aT(n/b) + f(n)`的递归方程。其中,a是每次递归调用的子问题数量,b是子问题规模缩小的比例,f(n)是基本操作的数量。 - 主定理提供了三个...
关于递归算法时间复杂度分析的探讨,是一个深入理解算法效率和优化的关键议题。递归,作为解决问题的一种强大工具,其本质是将复杂问题分解为更简单的子问题,通过求解这些子问题来达到最终解决方案的目的。然而,...
文中还探讨了线性复杂度的具体表示形式,如2^n-2^c,其中c是满足2≤r≤n-1,1≤c≤2^(n-2)的一个整数。同时,还讨论了如何通过给定的汉明重量来确定序列条数。 总结而言,文档涉及了密码学中的线性复杂度概念,特别...
在算法分析与研究中,时间复杂度的分析是一项核心内容。算法的时间复杂度通常指的是算法运行时间随输入数据规模增长的变化趋势。对于非递归算法来说,时间复杂度的分析相对直观,而对于递归算法,由于其自身的调用...
5. **常见时间复杂度计算**:常见的算法时间复杂度有O(1)常数时间,O(logN)对数时间,O(N)线性时间,O(NlogN)线性对数时间,O(N^2)平方时间等。例如,Func2的时间复杂度为O(2N)即O(N),Func3的时间复杂度取决于循环...
时间复杂度是算法分析与研究的重要内容,通常用重复执行次数最多的语句频度来分析算法的时间复杂度。例如,对n个存放于数组a[n]中的数进行选择法排序的算法,时间复杂度为t(n) = (n2 - n) = O(n2)。然而,对一个算法...
算法设计与分析——时间复杂度 算法设计与分析是计算机科学中的一门重要课程,旨在研究和分析算法的设计、实现和优化。时间复杂度是算法设计与分析的核心概念之一,指的是算法执行所需的时间成本。了解时间复杂度...
为了准确地分析递归算法的时间复杂度,我们需要建立并求解递归方程。 例如,分治法中的最大最小值查找算法可以通过递归方式实现。对于一个包含`n`个元素的数组,通过递归调用来寻找数组中的最大值和最小值。该递归...
7. 递归算法和循环算法在斐波那契数列计算中的应用:递归算法的时间复杂度为 O(2^n),循环算法的时间复杂度为 O(n)。 8. 递归算法和循环算法在二分查找算法中的应用:递归算法和循环算法的时间复杂度都为 O(logn),...
主定理通过分析递归式的形式,给出一个相对简单的解决方案。理解并应用主定理,能够帮助我们在设计算法时,快速预估算法的性能。 递推关系式则是另一类描述算法复杂度的形式,它通过上一步或几步的状态来描述当前...
6. O(2^n) - 指数时间复杂度:某些递归问题,如二进制搜索树的最差情况,执行时间呈指数增长。 7. O(n!) - 阶乘时间复杂度:旅行商问题、全排列等问题,执行时间与输入数据的阶乘成正比,通常在实际应用中要避免。 ...
以下是对几种常见排序算法的稳定性和时间复杂度的详细分析。 #### 1. 冒泡排序 冒泡排序是一种简单的排序算法,通过重复地遍历待排序的列表,比较每对相邻项,并在必要时交换它们。这一过程会持续进行,直到不再...
《西南交通大学算法分析与设计实验报告 - 染色问题时间复杂度》 算法分析与设计是计算机科学中的核心课程,旨在深入理解算法的工作原理及其效率。本实验报告聚焦于染色问题的时间复杂度分析,具体是针对mColoring...
以下是对选择排序、冒泡排序、归并排序、快速排序和插入排序这五种常见排序算法的详细介绍,以及如何分析它们的时间复杂度。 1. **选择排序(Selection Sort)** - 原理:选择排序是一种简单直观的排序算法,它...
### 数据结构算法分析 #### 插入类排序 **直接插入排序** - **定义与特点**:直接插入排序是一种简单的排序方法,适用于小规模或基本有序的数据集。 - **时间复杂度**: - 平均时间复杂度:\(O(n^2)\) - 最坏...
本文将详细介绍几种常见的排序算法,并分析它们的时间复杂度及稳定性。 #### 二、排序算法概述 1. **选择排序** - **定义**:选择排序是一种简单直观的比较排序算法。它的工作原理是通过在未排序序列中找到最小...