《计算机算法设计与分析》笔记
第一章 算法概述
1.1算法性质：
输入、输出、确定性、有限性
1.2时间复杂度
-
上界记号O：如果存在正的常数C和自然数N0，使得当N≧N0时有f(N)≦Cg(N)，则f(N)有上界函数g(N)，记为f(N)= O(g(N))。
-
同阶记号θ：f(N)=θ(g(N))表示f(N)和g(N)同阶 。
-
下界记号Ω：如果存在正的常数C和自然数N0，使得当N≧N0 时有f(N)≧Cg(N)，则f(N)有下界函数g(N)，记为f(N) = Ω(g(N))。
1.3NP完全性理论
P类问题：是指一类能够用确定性算法在多项式时间内求解的判定问题。其实，在非正式的定义中，我们可以把那些在多项式时间内求解的问题当作P类问题。
NP类问题：是指一类可以用不确定性多项式算法求解的判定问题。（不确定性算法：非确定(“猜想”)阶段+确定(“验证”)阶段）
第二章 递归与分治策略
2.1 递归
递归算法是一个直接或间接地调用自己的算法。
例1：阶乘函数
int fac(int n)
{ if (n==0) return 1;return n*fac(n-1);
}
例2：Hanoi塔问题。
汉诺塔问题可以通过以下三个步骤实现：
（1）将塔A上的n-1个碟子借助塔C先移到塔B上。
（2）把塔A上剩下的一个碟子移到塔C上。
（3）将n-1个碟子从塔B借助塔A移到塔C上。
void move(char x,char y)
{printf("%c->%c\n",x,y);
}void hanoi(int n, char a, char b, char c){if (n == 1) move(a,c);else { hanoi(n-1, a, c, b); move(a,c); hanoi(n-1, b, a, c);
}
例3：多变元递归——整数划分问题
例：整数划分问题：将一个正整数n表示为一系列正整数之和，n = n1 + n2 +…+nk 其中n1≥n2≥…≥nk≥1, k≥1。
例如 p(6) = 11 ，即整数6的划分数为11种：
6, 5+1, 4+2, 4+1+1, 3+3, 3+2+1, 3+1+1+1, 2+2+2, 2+2+1+1, 2+1+1+1+1, 1+1+1+1+1+1
最简单情形：(1) q(n, 1)=1，q(1, m) =1 n, m≥1;
递归关系： (2) q(n, n) = 1 + q(n, n–1)，n＞1;
产生的新情况： (3) q(n, m) = q(n, m–1) + q(n–m, m), n＞m＞1
划分中不含m的情况 划分中含m的情况 (4) q(n, m) = q(n, n), n＜m。
例4：多步递归——Fibonacci数列
2.2分治法
解型为T(n)=aT(n/b)+O(nd)的递归方程
设a>=1和b>1是常数，f(n)是一个函数，
T(n)是定义在非负整数集上的函数：T(n)=aT(n/b)+ O(nd) 。
例1：二分搜索技术
int BinarySearch(Type a[ ], const Type &x, int n)
{int left=0;int right=n-1;while (left <= right ){ int middle = (left+right)/2;if (x == a[middle]) return middle;if (x < a[middle]) right = middle-1; else left = middle+1;}return -1;
}
例2：大整数的乘法
