数据结构：时间复杂度空间复杂度(递归)

转载文章

时间复杂度：

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，进而分析f(n)随n的变化情况并确定T(n)的数量级。这里用"O"来表示数量级，给出算法的时间复杂度。

T(n)=O(f(n));

它表示随着问题规模的n的增大，算法的执行时间的增长率和f(n)的增长率相同，这称作算法的渐进时间复杂度，简称时间复杂度。而我们一般讨论的是最坏时间复杂度，这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，分析最坏的情况以估算算法指向时间的一个上界。

时间复杂度的分析方法：

1、时间复杂度就是函数中基本操作所执行的次数
2、一般默认的是最坏时间复杂度，即分析最坏情况下所能执行的次数
3、忽略掉常数项
4、关注运行时间的增长趋势，关注函数式中增长最快的表达式，忽略系数
5、计算时间复杂度是估算随着n的增长函数执行次数的增长趋势
6、递归算法的时间复杂度为：递归总次数 * 每次递归中基本操作所执行的次数

常用的时间复杂度有以下七种，算法时间复杂度依次增加：O(1)常数型、O(log2 n)对数型、O(n)线性型、O(nlog2n)二维型、O(n^2)平方型、O(n^3)立方型、O(2^n)指数型.

空间复杂度：

算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数，与问题的规模没有关系。算法的空间复杂度S(n)定义为该算法所耗费空间的数量级。

S(n)=O(f(n)) 若算法执行时所需要的辅助空间相对于输入数据量n而言是一个常数，则称这个算法的辅助空间为O(1);

递归算法的空间复杂度：递归深度N*每次递归所要的辅助空间，如果每次递归所需的辅助空间是常数，则递归的空间复杂度是 O(N).

进一步分析：

两段算法串联在一起的复杂度 T1(n) + T2(n) = max( O(f1(n)) + O(f2(n)) ) ，即比较慢的那个算法决定了串联后的效率。

两段算法嵌套在一起的复杂度 T1(n) * T2(n) = O( f1(n) * f2(n) )。

if - else 结构的复杂度取决于if条就爱你判断复杂度和两个分枝部分的复杂度，总体复杂度取三者中最大。即度结构

If(p1) /*p1 的复杂度为O(f1)*/

P2;/*p2 的复杂度为O(f2)*/

else

P3 /*p3 的复杂度为O(f3)*/

总复杂度为max(O(f1),O(f2),O(f3)).

例：

1、求二分法的时间复杂度和空间复杂度。

非递归：

template<typename T>
T* BinarySearch(T* array,int number,const T& data)
{assert(number>=0);int left = 0;int right = number-1;while (right >= left){int mid = (left&right) + ((left^right)>>1);if (array[mid] > data){right = mid - 1;}else if (array[mid] < data){left = mid + 1;}else{return (array + mid);}}return NULL;
}

分析：

循环的基本次数是log2 N，所以:

时间复杂度是O(log2 N);

由于辅助空间是常数级别的所以：

空间复杂度是O(1);

递归：

template<typename T>
T* BinarySearch(T* left,T* right,const T& data)
{assert(left);assert(right);if (right >=left){T* mid =left+(right-left)/2;if (*mid == data)return mid;elsereturn *mid > data ? BinarySearch(left, mid - 1, data) : BinarySearch(mid + 1, right, data);}else{return NULL;}
}

递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的：

时间复杂度:O(log2 N)

空间复杂度：O(log2N )

2、斐波那契数列的时间和空间复杂度

//递归情况下的斐波那契数列

long long Fib(int n)
{assert(n >= 0);return n<2 ? n : Fib(n - 1) + Fib(n-2);
}

递归的时间复杂度是：递归次数*每次递归中执行基本操作的次数

所以时间复杂度是： O(2^N)

递归的空间复杂度是：递归的深度*每次递归所需的辅助空间的个数

所以空间复杂度是：O(N)

说明一下：为什么这里空间复杂度是O(N)?

辅助空间指的是为局部变量和形参所开辟的空间，这有形参，需要分配一个存储单元。

对于递归算法，由于运行时有附加堆栈，所以递归的空间复杂度是递归的深度*每次压栈所需的空间个数。

递归有运行时堆栈，求的是递归最深的那一次压栈所耗费的空间的个数递归最深的那一次所耗费的空间足以容纳它所有递归过程。（递归是要返回上一层的，所以它所需要的空间不是一直累加起来的）

所以最深的那次压栈就是递归的空间复杂度。

举个栗子：现在有一个Stack，现在向里面push数据 push(1) , push(2) , pop(2) , push(3) 总共向里面push了3次数据，但是栈的深度为2，所需要栈的大小也为2. 这与递归是一样的，它堆栈最深的那一次所开辟的空间就是它所耗费空间的个数。

所以，递归的深度是n，而每次递归所需的辅助空间个数为1.

//求前n项中每一项的斐波那契数列的值

long long *Fib(int  n)
{assert(n>=0);long long *array = new long long[n + 1];array[0] = 0;if (n > 0){array[1] = 1;}for (int i = 2; i <n+1; i++){array[i] = array[i - 1] + array[i - 2];}return array;
}

循环的基本操作次数是n-1,辅助空间是n+1，所以：

时间复杂度O(n)

空间复杂度O(n)

//非递归

long long Fib(int n)
{assert(n >= 0);long long first=0,second=1;for (int i = 2; i <= n; i++){first = first^second;second = first^second;first = first^second;second = first + second;}return second;
}

循环的基本次数是n-1，所用的辅助空间是常数级别的：

时间复杂度：O(n)

空间复杂度：O(1)

最大子列和问题：

（思想：分而治之）

给定K个整数组成的序列{ N1, N2, ..., NK }，“连续子列”被定义为{ Ni, Ni+1, ..., Nj }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

视频讲解：

核心代码：

int Max3( int A, int B, int C ){ /* 返回3个整数中的最大值 */return A > B ? A > C ? A : C : B > C ? B : C;}int DivideAndConquer( int List[], int left, int right ){ /* 分治法求List[left]到List[right]的最大子列和 */int MaxLeftSum, MaxRightSum; /* 存放左右子问题的解 */int MaxLeftBorderSum, MaxRightBorderSum; /*存放跨分界线的结果*/int LeftBorderSum, RightBorderSum;int center, i;if( left == right )  { /* 递归的终止条件，子列只有1个数字 */if( List[left] > 0 )  return List[left];else return 0;}/* 下面是"分"的过程 */center = ( left + right ) / 2; /* 找到中分点 *//* 递归求得两边子列的最大和 */MaxLeftSum = DivideAndConquer( List, left, center );MaxRightSum = DivideAndConquer( List, center+1, right );/* 下面求跨分界线的最大子列和 */MaxLeftBorderSum = 0; LeftBorderSum = 0;for( i=center; i>=left; i-- ) { /* 从中线向左扫描 */LeftBorderSum += List[i];if( LeftBorderSum > MaxLeftBorderSum )MaxLeftBorderSum = LeftBorderSum;} /* 左边扫描结束 */MaxRightBorderSum = 0; RightBorderSum = 0;for( i=center+1; i<=right; i++ ) { /* 从中线向右扫描 */RightBorderSum += List[i];if( RightBorderSum > MaxRightBorderSum )MaxRightBorderSum = RightBorderSum;} /* 右边扫描结束 *//* 下面返回"治"的结果 */return Max3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum );}int MaxSubseqSum3( int List[], int N ){ /* 保持与前2种算法相同的函数接口 */return DivideAndConquer( List, 0, N-1 );}

时间复杂度的计算：