麻省理工公开课《算法导论》，的确比看书有意思很多。第三节课分治法，的确让我受益匪浅！通过在网上查找总结 了这节课的部分用到分治思想的算法，权当笔记。
（一）归并排序：
#include <stdio.h>#include <stdlib.h>#include <string>typedef long long LL;using namespace std;/* T(n) = 2T(n/2) + ⊙(n) = nlog(n) */void Merge_sort(int *A,int x,int y,int *t) /* x表示左闭，y表示右开 */{if(y – x > 1){int m = x + (y – x) / 2;int p = x,q = m,i = x;Merge_sort(A, x, m, t);Merge_sort(A, m, y, t);while(p < m || q < y){if(q >= y || (p < m && A[p] <= A[q]))t[i++] = A[p++];else t[i++] = A[q++];}for(i=x; i<y; i++)A[i] = t[i];} } int main(){int t[15];int s[] = {4, 1, 7, 6, 3, 8, 2, 5, 0, 9};Merge_sort(s, 0, 10, t);int i;for(i=0; i<10; i++)printf("%d ", s[i]);printf("\n");return 0;}
（二）二分查找：
用递归体会一下其中的分治思想，，当然也可以用while循环解决！
#include <stdio.h>#include <stdlib.h>#include <string>typedef long long LL;using namespace std;/* T(n) = T(n/2) + ⊙(1) = log(n) */int Binary_find(int key, int left, int right, int *a){int mid = left + (right – left) / 2;if(a[mid] == key) return mid;else if(a[mid] > key) return Binary_find(key, left, mid – 1, a);else if(a[mid] < key) return Binary_find(key, mid + 1, right, a);}int main(){int a[] = {1, 3, 4, 6, 7, 9, 12, 14, 23, 24};int i;int ans;for(i=0; i<8; i++){ans = Binary_find(a[i], 0, 7, a);printf("%d\n", ans);}return 0;}（三）x的n次方：
库函数<math.h>里面的double pow(double x, double y) 更加完美，指数可以是浮点型。这里手写个double Pow(double x, int n)。
#include <stdio.h>#include <stdlib.h>#include <string>typedef long long LL;using namespace std;/* T(n) = T(n/2) + ⊙(1) = log(n) */double f(double x, int n){if(1 == n) return x;int mid = (n>>1);double s = f(x, mid);if(n & 1) return s * s * x;else return s * s;}double Pow(double x, int n){if(0 == x && n > 0) return 0.0;else if(0 == n) return 1.0;else if(n > 0) return f(x, n);else if(n < 0) return (1/f(x, -n));}int main(){double x;int n;while(~scanf("%lf%d", &x, &n)){printf("%0.6lf\n", Pow(x, n));printf("%0.6lf\n", pow(x, n));}}（四）斐波那契(Fibonacci)数列：
递归是最愚蠢的做法，迭代可以是⊙(n) 的复杂度，矩阵快速幂可达到⊙(log(n)) 的复杂度。
F(n) 表示第n个斐波那契数则有这样的关系：
矩阵 F(N+1) F(N) = 矩阵 1 1 的 N 次方
F(N) F(N-1) 1 0
可用数学归纳法证明。所以结果就是普通的矩阵快速幂。
#include <stdio.h>#include <stdlib.h>#include <string.h>#include <windows.h>#include <iostream>using namespace std;int cnt;/* 时间复杂度为指数级 */LL Fibonacci(int n){cnt++;if(1 == n || 2 == n) return 1;else return Fibonacci(n – 1) + Fibonacci(n – 2);}/* T(n) = ⊙(n) */LL Fibonacci1(int n){LL a[100000];a[1] = a[2] = 1;int i;for(i=3; i<=n; i++)a[i] = a[i – 1] + a[i – 2];return a[n];}typedef struct{LL a[2][2];}Matrix;Matrix A, B;Matrix Matrix_mul(Matrix X, Matrix Y) {Matrix tmp;memset(tmp.a, 0, sizeof(tmp));int i,j,k;for(i=0; i<2; i++)for(j=0; j<2; j++)for(k=0; k<2; k++)tmp.a[i][j] += X.a[i][k] * Y.a[k][j];return tmp; } /* T(n) = ⊙(logn) */LL Fibonacci2(int n){A.a[0][0] = 1;A.a[0][1] = 1;A.a[1][0] = 1;A.a[1][1] = 0;B.a[0][0] = 1;B.a[0][1] = 0;B.a[1][0] = 0;B.a[1][1] = 1;while(n){if(n & 1) B = Matrix_mul(B, A);A = Matrix_mul(A, A);n >>= 1;}return B.a[0][0];}int main(){int i;int text = 4;LL ans = Fibonacci1(text);//long begtime = clock();FILETIME beg,end;GetSystemTimeAsFileTime(&beg); for(i=0; i<100000; i++)Fibonacci2(text);GetSystemTimeAsFileTime(&end);long time = (end.dwLowDateTime-beg.dwLowDateTime); //long endtime = clock();//cout<<endtime – begtime<<endl; cout << time <<endl;cout << ans <<endl;}（五）斯特拉森(Strassen)矩阵乘法：
参考了网上的做法，重写了此矩阵乘法，用了一个4阶矩阵验证。在此不得不吐槽下，百度百科和维基百科里的信息貌似都有误，其中百度百科里c22=m5-m3+m2-m1应该改为c22=m5-m3+m2-m7。最后还是参考了麻省公开课里的年轻教授的板书才改回来（自己居然没有把式子展开验证的勇气╮(╯_╰)╭）。
我们可以失望，但不能盲目。
