2020-10-05

讨论1.6 算法3的空间复杂度是多少？ 老师参与 具体来说，这个问题分两部分： 由于递归而产生的空间复杂度是多少？ 算法的整体空间复杂度一共是多少？

分而治之的算法

时间复杂度

T(N)=2T(N/2)+O(N) =2(2T(N/(2^2))+cN/2)+cN =2^kO(1)+ckN 其中N/(2^k)=1 k=log2(N)

1.空间复杂度

1.整体

假如 n 个数据，中间一分为二，求左边空间要 n/2，右边也是一样。 跨越分界线的部分需要扫描一遍左边和右边，加起来是 n 所以总共是 S(n) = 2n

2.递归

递归一次，需要借助一个栈的单位空间来存储。 F(N)先入栈，然后分为两个F(N/2)，再入栈，再分，然后直到当前数字个数为1时即F(1)，函数才从下往上出栈，此时未出栈时为占用栈空间最大的时候，n/(2^k)=1，即k=logN。所以空间复杂度为S(logN)。 如果画一个图的话会更清晰一些，是一个二叉树。 刚开始思考的时候，以为要把所有从根结点到叶子结点的路径的深度都要加起来，但是想清楚了之后明白，只需要计算从根节点到最深的那个叶子结点的路径的深度就可以，它是一次访问到最底层的最左边的结点，再去这个叶子节点的兄弟结点，然后出栈。 总结就是，它会多次达到所需要的最大的栈空间（次数应该是叶子结点个数），而不是一次用更多的栈空间。所以空间复杂度就是树的深度。

补充 x=a<b?c:d 先判断？前面的语句，如果a小于b，x就等于c，否则x=d

分治法代码

int Max3(int A,int B,int C) { return A>B?(A>C?A:C):(B>C?B:C); /意思是若A>B，则返回(A > C ? A : C )，即若A还大於C，则返回A，否则返回C；若A小於等於B，则返回(B > C ? B : C)，即若B还大於C，则返回B，否则返回C；简单地说，此语句意思是返回A,B,C中最大的那个./ } int DivideAndConquer(int List[], int left, int right ) { int MaxLeftSum,MaxRightSum; int MaxLeftBorderSum,MaxRightBorderSum;

int LeftBorderSum,RightBorderSum; int center, i; if(Left = Right){#递归中止条件 if(List[left]>0) return List[left]; else return 0; } /* 下面是"分"的过程 */ center = (left+right)/2; /* 递归求得两边子列的最大和 */ MaxLeftSum = DivideAndConquer(int List[], int left, int center ); MaxRightSum = DivideAndConquer(int List[], int center+1, int right ); /* 下面求跨分界线的最大子列和 */ MaxLeftBorderSum = 0; LeftBorderSum = 0; #向左扫描 for(int i = center;i>0;i--) { LeftBorderSum += List[i]; if(LeftBorderSum>MaxLeftBorderSum) MaxLeftBorderSum=LeftBorderSum; } for(int i = center;i<right;i++) { RightBorderSum += List[i]; if(RightBorderSum>MaxRightBorderSum) MaxRightBorderSum=RightBorderSum; } return Max3(MaxRightBorderSum+MaxLeftBorderSum,MaxLeftSum,MaxRightSum);

} int MaxSubseqSum3( int List[], int N ) { /* 保持与前2种算法相同的函数接口 */ return DivideAndConquer( List, 0, N-1 ); }