基于主定理以及递推树求解递归算法的时间复杂度
非递归算法的时间复杂度可以通过找到执行次数最多的代码,计算其执行次数即可。但是递归算法的时间复杂度则无法通过这种方式求得。有一种最简单的求递归算法的方式,即利用递推方法求解时间复杂度。如下所示:
这种方法求时间复杂度很简单,但是可以如此简单的使用这种方法的情况很少,往往需要比较复杂的公式推导。因此利用这种方法求时间复杂度比较困难,需要利用别的方式进行求导。主要是以下两种方式:主定理、递推树。
1.主定理
递归算法的时间复杂度定义一般有如下形式:
在大部分情况下,可以通过主定理,求解该问题的时间复杂度。
注:要求 a大于等于1,b大于1,且f(n)为正函数。
计算步骤
其中,规则1,2是比较简单就可以计算出来的,规则3则比较复杂。
例题1
通过计算可得:
而f(n)的时间复杂度为O(1)=O(n^(2-2)),也就是说
符合第一种情况,则
例题2
通过计算可得:
而f(n)的时间复杂度为O(n)=O(n),也就是说,二者相等。
符合第二种情况,则
例题3
通过计算可得:
这种情况则应该套用规则三,
根据主定理的第三种规则,时间复杂度为:
反例
主定理求解的步骤不是很复杂,大部分的情况利用该定理可以得到解决,但是也有无法解决的情况:
由于这种情况,单纯的使用主定理已经无法解决了,因此引入递归树的求解方法。
递归树
基本原理如下所示:
递归树求解递归算法的时间复杂度,没有无法求解的情况,可能有的情况下求解时间复杂度很复杂,但是本质上都是可以求得的。
例题1
这种情况比较简单,但是里面有一个比较容易混淆的地方,在第二行的n/2,代表着数据量为n/2时,时间复杂度为n/2。这里代表的是时间复杂度,而不是数据量 。看下面这个例子,
在第二层,分出了4个枝杈,这代表着表达式中的4。但是这4个枝杈,左边的两个代表 第一个n/2的,右边的两个代表第二个n/2的。简而言之,递归树的层数,需要看T()的括号里面,而每一层的分支数,则需要看C*T()中的C。
例题2
这是主定理无法解决的那种情况,我们通过递归树来求一下。结果如下所示:
努力加油a啊
基于主定理以及递推树求解递归算法的时间复杂度
非递归算法的时间复杂度可以通过找到执行次数最多的代码,计算其执行次数即可。但是递归算法的时间复杂度则无法通过这种方式求得。有一种最简单的求递归算法的方式,即利用递推方法求解时间复杂度。如下所示:
这种方法求时间复杂度很简单,但是可以如此简单的使用这种方法的情况很少,往往需要比较复杂的公式推导。因此利用这种方法求时间复杂度比较困难,需要利用别的方式进行求导。主要是以下两种方式:主定理、递推树。
1.主定理
递归算法的时间复杂度定义一般有如下形式:
在大部分情况下,可以通过主定理,求解该问题的时间复杂度。
注:要求 a大于等于1,b大于1,且f(n)为正函数。
计算步骤
其中,规则1,2是比较简单就可以计算出来的,规则3则比较复杂。
例题1
通过计算可得:
而f(n)的时间复杂度为O(1)=O(n^(2-2)),也就是说
符合第一种情况,则
例题2
通过计算可得:
而f(n)的时间复杂度为O(n)=O(n),也就是说,二者相等。
符合第二种情况,则
例题3
通过计算可得:
这种情况则应该套用规则三,
根据主定理的第三种规则,时间复杂度为:
反例
主定理求解的步骤不是很复杂,大部分的情况利用该定理可以得到解决,但是也有无法解决的情况:
由于这种情况,单纯的使用主定理已经无法解决了,因此引入递归树的求解方法。
递归树
基本原理如下所示:
递归树求解递归算法的时间复杂度,没有无法求解的情况,可能有的情况下求解时间复杂度很复杂,但是本质上都是可以求得的。
例题1
这种情况比较简单,但是里面有一个比较容易混淆的地方,在第二行的n/2,代表着数据量为n/2时,时间复杂度为n/2。这里代表的是时间复杂度,而不是数据量 。看下面这个例子,
在第二层,分出了4个枝杈,这代表着表达式中的4。但是这4个枝杈,左边的两个代表 第一个n/2的,右边的两个代表第二个n/2的。简而言之,递归树的层数,需要看T()的括号里面,而每一层的分支数,则需要看C*T()中的C。
例题2
这是主定理无法解决的那种情况,我们通过递归树来求一下。结果如下所示:
努力加油a啊