• 递归函数时间复杂度分析
千次阅读
2016-09-23 00:55:25

递归函数时间复杂度分析

(1) 递归执行过程
例子：求N!。
这是一个简单的”累乘”问题，用递归算法也能解决。
n! = n * (n - 1)! n > 1
0! = 1, 1! = 1 n = 0,1
因此，递归算法如下：

Java代码
fact(int n) {
if(n == 0 || n == 1)
return 1;
else
return n * fact(n - 1);
}
以n=3为例，看运行过程如下：
fact(3) —– fact(2) —– fact(1) —— fact(2) —–fact(3)
——————————> ——————————>
递归 回溯
递归算法在运行中不断调用自身降低规模的过程，当规模降为1，即递归到fact(1)时，满足停止条件停止递归，开始回溯(返回调用算法)并计算，从fact(1)=1计算返回到fact(2);计算2*fact(1)=2返回到fact(3)；计算3*fact(2)=6，结束递归。
算法的起始模块也是终止模块。
(2) 递归实现机制
每一次递归调用，都用一个特殊的数据结构”栈”记录当前算法的执行状态，特别地设置地址栈，用来记录当前算法的执行位置，以备回溯时正常返回。递归模块的形式参数是普通变量，每次递归调用得到的值都是不同的，他们也是由”栈”来存储。
(3) 递归调用的几种形式
一般递归调用有以下几种形式(其中a1、a2、b1、b2、k1、k2为常数)。
<1> 直接简单递归调用： f(n) {…a1 * f((n - k1) / b1); …};

<2> 直接复杂递归调用： f(n) {…a1 * f((n - k1) / b1); a2 * f((n - k2) / b2); …};
<3> 间接递归调用： f(n) {…a1 * f((n - k1) / b1); …}，
g(n) {…a2 * f((n - k2) / b2); …}。
2. 递归算法效率分析方法
递归算法的分析方法比较多，最常用的便是迭代法。
迭代法的基本步骤是先将递归算法简化为对应的递归方程，然后通过反复迭代，将递归方程的右端变换成一个级数，最后求级数的和，再估计和的渐进阶。
<1> 例：n!
算法的递归方程为： T(n) = T(n - 1) + O(1);
迭代展开： T(n) = T(n - 1) + O(1)
= T(n - 2) + O(1) + O(1)
= T(n - 3) + O(1) + O(1) + O(1)
= ……
= O(1) + … + O(1) + O(1) + O(1)
= n * O(1)
= O(n)
这个例子的时间复杂性是线性的。
<2> 例：如下递归方程：

  T(n) = 2T(n/2) + 2, 且假设n=2的k次方。
T(n) = 2T(n/2) + 2
= 2(2T(n/2*2) + 2) + 2
= 4T(n/2*2) + 4 + 2
= 4(2T(n/2*2*2) + 2) + 4 + 2
= 2*2*2T(n/2*2*2) + 8 + 4 + 2
= ...
= 2的(k-1)次方 * T(n/2的(i-1)次方) + \$(i:1~(k-1))2的i次方
= 2的(k-1)次方 + (2的k次方)  - 2
= (3/2) * (2的k次方) - 2
= (3/2) * n - 2
= O(n)
这个例子的时间复杂性也是线性的。


<3> 例：如下递归方程：

  T(n) = 2T(n/2) + O(n), 且假设n=2的k次方。
T(n) = 2T(n/2) + O(n)
= 2T(n/4) + 2O(n/2) + O(n)
= ...
= O(n) + O(n) + ... + O(n) + O(n) + O(n)
= k * O(n)
= O(k*n)
= O(nlog2n) //以2为底

一般地，当递归方程为T(n) = aT(n/c) + O(n), T(n)的解为：
O(n)          (a<c && c>1)
O(nlog2n)     (a=c && c>1) //以2为底
O(nlogca)     (a>c && c>1) //n的(logca)次方，以c为底


上面介绍的3种递归调用形式，比较常用的是第一种情况，第二种形式也有时出现，而第三种形式(间接递归调用)使用的较少，且算法分析
比较复杂。 下面举个第二种形式的递归调用例子。
<4> 递归方程为：T(n) = T(n/3) + T(2n/3) + n
为了更好的理解，先画出递归过程相应的递归树：
n ——–> n
n/3 2n/3 ——–> n
n/9 2n/9 2n/9 4n/9 ——–> n
…… …… …… ……. ……
——–
总共O(nlogn)
累计递归树各层的非递归项的值，每一层和都等于n，从根到叶的最长路径是：

  n --> (2/3)n --> (4/9)n --> (12/27)n --> ... --> 1
设最长路径为k，则应该有：

(2/3)的k次方 * n = 1
得到 k = log(2/3)n  // 以(2/3)为底
于是 T(n) <= (K + 1) * n = n (log(2/3)n + 1)
即 T(n) = O(nlogn)
由此例子表明，对于第二种递归形式调用，借助于递归树，用迭代法进行算法分析是简单易行的。 递归 递归算法
更多相关内容
• 原文链接：... This page documents the time-complexity (aka "Big O" or "Big Oh") of various operations in current CPython. Other Python implementations (or older or ...

This page documents the time-complexity (aka "Big O" or "Big Oh") of various operations in current CPython. Other Python implementations (or older or still-under development versions of CPython) may have slightly different performance characteristics. However, it is generally safe to assume that they are not slower by more than a factor of O(log n).

Generally, 'n' is the number of elements currently in the container. 'k' is either the value of a parameter or the number of elements in the parameter.

# list

The Average Case assumes parameters generated uniformly at random.

Internally, a list is represented as an array; the largest costs come from growing beyond the current allocation size (because everything must move), or from inserting or deleting somewhere near the beginning (because everything after that must move). If you need to add/remove at both ends, consider using a collections.deque instead.

 Operation Average Case Copy O(n) O(n) Append O(1) O(1) Pop last O(1) O(1) Pop intermediate O(k) O(k) Insert O(n) O(n) Get Item O(1) O(1) Set Item O(1) O(1) Delete Item O(n) O(n) Iteration O(n) O(n) Get Slice O(k) O(k) Del Slice O(n) O(n) Set Slice O(k+n) O(k+n) Extend O(k) O(k) O(n log n) O(n log n) Multiply O(nk) O(nk) x in s O(n) min(s), max(s) O(n) Get Length O(1) O(1)

# collections.deque

A deque (double-ended queue) is represented internally as a doubly linked list. (Well, a list of arrays rather than objects, for greater efficiency.) Both ends are accessible, but even looking at the middle is slow, and adding to or removing from the middle is slower still.

 Operation Average Case Amortized Worst Case Copy O(n) O(n) append O(1) O(1) appendleft O(1) O(1) pop O(1) O(1) popleft O(1) O(1) extend O(k) O(k) extendleft O(k) O(k) rotate O(k) O(k) remove O(n) O(n)

# set

See dict -- the implementation is intentionally very similar.

 Operation Average case Worst Case notes x in s O(1) O(n) Union s|t Intersection s&t O(min(len(s), len(t)) O(len(s) * len(t)) replace "min" with "max" if t is not a set Multiple intersection s1&s2&..&sn (n-1)*O(l) where l is max(len(s1),..,len(sn)) Difference s-t O(len(s)) s.difference_update(t) O(len(t)) Symmetric Difference s^t O(len(s)) O(len(s) * len(t)) s.symmetric_difference_update(t) O(len(t)) O(len(t) * len(s))
• As seen in the source code the complexities for set difference s-t or s.difference(t) (set_difference()) and in-place set difference s.difference_update(t) (set_difference_update_internal()) are different! The first one is O(len(s)) (for every element in s add it to the new set, if not in t). The second one is O(len(t)) (for every element in t remove it from s). So care must be taken as to which is preferred, depending on which one is the longest set and whether a new set is needed.

• To perform set operations like s-t, both s and t need to be sets. However you can do the method equivalents even if t is any iterable, for example s.difference(l), where l is a list.

# dict

The Average Case times listed for dict objects assume that the hash function for the objects is sufficiently robust to make collisions uncommon. The Average Case assumes the keys used in parameters are selected uniformly at random from the set of all keys.

Note that there is a fast-path for dicts that (in practice) only deal with str keys; this doesn't affect the algorithmic complexity, but it can significantly affect the constant factors: how quickly a typical program finishes.

 Operation Average Case Amortized Worst Case Copy O(n) O(n) Get Item O(1) O(n) Set Item O(1) O(n) Delete Item O(1) O(n) Iteration O(n) O(n)

 = These operations rely on the "Amortized" part of "Amortized Worst Case". Individual actions may take surprisingly long, depending on the history of the container.

 = For these operations, the worst case n is the maximum size the container ever achieved, rather than just the current size. For example, if N objects are added to a dictionary, then N-1 are deleted, the dictionary will still be sized for N objects (at least) until another insertion is made.

展开全文 • 转自：http://blog.csdn.net/flyfish1986/article/details/46994347  ... 函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n > N，f(n)总是比g(n)大，那么，我们说f(n)的增长渐近快

转自：http://blog.csdn.net/flyfish1986/article/details/46994347

http://www.cnblogs.com/SCAU_que/articles/1735784.html

函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n > N，f(n)总是比g(n)大，那么，我们说f(n)的增长渐近快于g(n)。

算法时间复杂度定义
在进行算法分析时，语句总的执行次数T(n）是关于问题规模n的函数，进而分析T(n）随n的变化情况并确定T(n）的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n）的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n）是问题规模n的某个函数。 这样用大写O( )来体现算法时间复杂度的记法，我们称之为大O记法。 一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。

推导大O阶：
1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中，只保留最高阶项。
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。得到的结果就是大O阶。

常用的时间复杂度所耗费的时间从小到大依次是
O(1) < O( logn ) < O( n ) < O( nlogn ) < O( n2 ) < O( n3 ) < O( 2n ) < O( n! ) < O( nn )

O(1)

Temp=i;i=j;j=temp;

以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时 间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

O(n^2)

2.1. 交换i和j的内容
sum=0； （一次）
for(i=1;i<=n;i++) （n次 ）
for(j=1;j<=n;j++) （n^2次 ）
sum++； （n^2次 ）
解：T(n)=2n^2+n+1 =O(n^2)

2.2.
for (i=1;i<n;i++)
{
y=y+1; ①
for (j=0;j<=(2*n);j++)
x++; ②
}
解： 语句1的频度是n-1
语句2的频度是(n-1)*(2n+1)=2n^2-n-1
f(n)=2n^2-n-1+(n-1)=2n^2-2
该程序的时间复杂度T(n)=O(n^2).

O(n)

2.3.
a=0;
b=1; ①
for (i=1;i<=n;i++) ②
{
s=a+b;　　　　③
b=a;　　　　　④
a=s;　　　　　⑤
}
解： 语句1的频度：2,
语句2的频度： n,
语句3的频度： n-1,
语句4的频度：n-1,
语句5的频度：n-1,
T(n)=2+n+3(n-1)=4n-1=O(n).

O(log2n )

2.4.
i=1; ①
while (i<=n)
i=i*2; ②
解： 语句1的频度是1,
设语句2的频度是f(n), 则：2^f(n)<=n;f(n)<=log2n
取最大值f(n)= log2n,
T(n)=O(log2n )

O(n^3)

2.5.
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
for(k=0;k<j;k++)
x=x+2;
}
}
解：当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n^3).

我们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最 坏情况运行时间是 O(n^2)，但期望时间是 O(nlogn)。通过每次都仔细 地选择基准值，我们有可能把平方情况 (即O(n^2)情况)的概率减小到几乎等于 0。在实际中，精心实现的快速排序一般都能以 (O(nlogn)时间运行。
下面是一些常用的记法：

访问数组中的元素是常数时间操作，或说O(1)操作。一个算法如 果能在每个步骤去掉一半数据元素，如二分检索，通常它就取 O(logn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间 。常规的矩阵乘算法是O(n^3)，因为算出每个元素都需要将n对 元素相乘并加到一起，所有元素的个数是n^2。
指数时间算法通常来源于需要求出所有可能结果。例如，n个元 素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的 。指数算法一般说来是太复杂了，除非n的值非常小，因为，在 这个问题中增加一个元素就导致运行时间加倍。不幸的是，确实有许多问题 (如著名 的“巡回售货员问题” )，到目前为止找到的算法都是指数的。如果我们真的遇到这种情况， 通常应该用寻找近似最佳结果的算法替代之
展开全文 • 时间复杂度计算 此笔记来源于左神算法，只用做笔记使用，已注明来源。 此事件复杂度只适用于递归算法，并且递归过程中要求数据规模大体相同 T(N)=a∗T(Nb)+O(Nd)T(N)=a*T\left(\frac{N}{b}\right)+O(N^d)T(N)=a∗T...

## 时间复杂度计算

此笔记来源于左神算法，只用做笔记使用，已注明来源。

此事件复杂度只适用于递归算法，并且递归过程中要求数据规模大体相同

T ( N ) = a ∗ T ( N b ) + O ( N d ) T(N)=a*T\left(\frac{N}{b}\right)+O(N^d)

• 1 当 log ⁡ b a > d \log_ba>d 复杂度为 O ( N log ⁡ b a ) O\left(N^{\log_ba}\right)
• 2 当 log ⁡ b a < d \log_ba<d 复杂度为 O ( N d ) O\left(N^d\right)
• 3 当 log ⁡ b a = d \log_ba=d 复杂度为 O ( N d × log ⁡ N ) O\left(N^d\times{\log{N}}\right)

a为将数据分成几块，b为每块数据占用总数据的数据量， O ( N d ) O(N^d) 为每迭代的时间复杂度,然后计算d的值

展开全文  算法
• 【list】的内置函数时间复杂度 方法复杂度简介 index[x] O(1) 索引 index assignment O(1) 索引赋值 append O(1) 尾部追加 pop() O(1) 尾部弹出 pop(i) O(n) 指定位置弹...
• python
• 导致很多函数都不太敢用了，于是总结一下常见的函数时间复杂度。 列表(List): list.copy()：平均和最坏时间复杂度都是O ( n ) list.append(obj)：平均和最坏时间复杂度都是O ( 1 ) list.pop(index)：index为-1的... python
• vector、map、queue 等 C++ 常用 STL的特性、函数时间复杂度和用法。 算法
• 算法的时间复杂度是一个函数，它定量描述了该算法的运行时间，时间复杂度常用“O”表述，使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况时间复杂度是用来估计算法运行时间的一个...
• I'm trying to figure what the time complexity of the count() function.Ex if there is a list of [1, 2, 2, 3] and [1, 2, 2, 3].count(2) is used.I've searched endlessly and looked at the Python wiki here...
• python各种内置函数时间复杂度 最近在做题的时候常常遇到题目对于时间复杂度的控制，虽然暴力的方法可以通过OJ，但是这样做并没有达到题目本身的目的。虽然自己代码中循环结构的时间复杂度可以控制，但是却不是很...
• 文章目录举个例子常见的时间复杂度最坏情况与平均情况 举个例子 int i,j; for(i=0;i<n;i++){ function(i);...function函数时间复杂度是O(1)，所以整体的时间复杂度就是循环的次数O(n)。 假如functi... 数据结构学习笔记
• 1. std::find template inline _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val, input_iterator_tag) { while (__first != __last &...时间复杂度是O(n). 2. map::f..
• 　实现字符串的反转函数 　1.字符串反转，找出位于整个字符串最中间的那个字符，然后将两边的字符对等交换位置。不必去循环遍历整个字符串的长度 二、实现 package com.test.util; public class Test1 { ... 字符串 java
• 函数递归调用的时间复杂度 首先关于这个话题，我们先介绍一下递归与时间复杂度两个概念： 递归 就我个人而言，我理解的概念就是在解决许多问题需要使用到许多重复的步骤的时候，就可以通过程序自身调用自身的方法... C语言
• sort函数进行排序的时间复杂度为n*log2n。 原理：不是简单的快排 STL的sort()算法,数据量大时采用Quick Sort,分段递归排序,一旦分段后的数据量小于某个门槛,为避免Quick Sort的递归调用带来过大的额外负荷,就改用...
• 这种说法是错误的。...)这需要O(log(b))乘法，并通过平方求幂，但是bignum乘法不是恒定时间，因此时间复杂度取决于所使用的乘法算法的细节。(另外，Python并不完全使用平方求幂，但是Python使用的仍然是O(...
• 任何一个分治或者递归的函数都可以算出它的时间复杂度 关键4种 二分查找:发生在一个数列本身有序的时候,要在有序的数列中找到你要的目标数,所以每次一分为2只查一边,最后时间复杂度是O(logN) 从 T(n) = T(n/2) + O(1...
• 下面介绍几种递归函数中的算法时间复杂度分析的方法 0.递推法 这种方法是最简单的，也是最容易理解的一种方法，对于一个递归函数，我们可以利用他的递归方程，将其递推到常量的情况下，这样子就很容易求解他的时间... 算法 二叉树 数据结构
• 算法复杂度分为时间复杂度和空间复杂度。 其作用： 时间复杂度是指执行算法所需要的计算工作量； 而空间复杂度是指执行这...算法的时间复杂度是一个函数，它定量描述了该算法的运行时间，时间复杂度常用“O”表述，使
• 进行算法不可避免对于相关性能进行分析 ，小编也是简单学习到了关于时间复杂度的相关东西，以及其不同的运算规律！ 算法导论
• java 数据结构
• 假设我们有一个数组，V，Vi表示V中的第i个元素，那么这个元素的Softmax第i个元素位置的输出就是 一般来说，Softmax输出的是一个向量，如果原向量长度是n，Softmax输出的向量长度就是n，计算的时间复杂度是O(n)。...
• 引言我们在使用python开发过程中，list属于使用非常广泛的数据结构。不管是自己程序存放数据，还是处理接口...所以我们要剖析下list的各个方法的时间复杂度，以帮助我们在业务开发中对应该怎样用list或者是否该用lis...  ...