算法分析与设计学习笔记---1
（一）学习须知
算法是什么：
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。
也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。
一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
为什么学习算法：
1.算法——程序的灵魂
问题的求解过程：
分析问题→设计算法→编写程序→整理结果
程序设计研究的四个层次：
算法→方法学→语言→工具
2.提高分析问题的能力
算法的形式化→思维的逻辑性、条理性
算法的五大特征
1.输入 2.输出 3.有穷性4.确定性5.可行性
渐进符号
- 大O符号
若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n))，或称算法在O(f(n)中。 - 大Ω符号
定义1.2 若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≥c×g(n)，则称T(n)=Ω(g(n)) - Θ符号
定义1.3 若存在三个正的常数c1、c2和n0，对于任意n≥n0都有c1×f(n)≥T(n)≥c2×f(n)，则称T(n)=Θ(f(n))
算法设计的一般过程
1．理解问题
2．预测所有可能的输入
3 在精确解和近似解间做选择
4 确定适当的数据结构
5．算法设计技术
6．描述算法
7．跟踪算法
8．分析算法的效率
9．根据算法编写代码
（二）例题
1.例： T(n)＝5n2＋8n＋1
当n≥1时，5n2＋8n＋1≤5n2＋8n＋n
＝5n2＋9n≤5n2＋9n2≤14n2＝O(n2)
当n≥1时，5n2＋8n＋1≥5n2＝Ω(n2)
∴ 当n≥1时，14n2≥5n2＋8n＋1≥5n2
则：5n2＋8n＋1＝Θ(n2)
定理1.1 若T(n)=amnm +am-1nm-1 + … +a1n+a0（am>0），则有T(n)=O(nm)且T(n)=Ω(n m)，因此，有T(n)=Θ(n m)。
2.扩展递归技术
（三）递推
递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。
递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。
例题1：
数字三角形
数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。
1、 一步可沿左斜线向下或右斜线向下走；
2、 三角形行数小于等于100；
3、 三角形中的数字为0，1，…，99；
测试数据通过键盘逐行输入，如上例数据应以如下所示格式输入：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
经过分析可以通过递推得到结果，用逆推来解决，将最后一层与倒数第二层分别相加取大值得到新的三角形，继续一层一层递推，最后的a[1][1]就是最大路径的和。
【参考程序】
#include
using namespace std;
int main()
{
int n,i,j,a[101][101];
cin>>n;
for (i=1;i<=n;i++)
for (j=1;j<=i;j++)
cin>>a[i][j]; //输入数字三角形的值
for (i=n-1;i>=1;i–)
for (j=1;j<=i;j++)
{
if (a[i+1][j]>=a[i+1][j+1]) a[i][j]+=a[i+1][j]; //路径选择
else a[i][j]+=a[i+1][j+1];
}
cout<<a[1][1]<<endl;
}
【例2】满足F1=F2=1，Fn=Fn-1+Fn-2的数列称为斐波那契数列（Fibonacci），它的前若干项是1，1，2，3，5，8，13，21，34……求此数 列第n项（n>=3）。
即：
f1=1 （n=1）
f2=1 （n=2）
fn=fn-1 + fn-2 （n>=3）
程序如下：
#include
#include
using namespace std;
int main()
{
int f0=1,f1=1,f2;
int n;
cin>>n;
for (int i=3; i<=n; ++i)
{
f2=f0+f1;
f0=f1;
f1=f2;
}
printf("%d\n",f2);
return 0;
}
斐波那切数列例子：上楼梯（一步两步），兔子繁殖
1.上楼梯
楼梯有n个台阶，上楼可以一步上一阶，也可以一步上两阶。一共有多少种上楼的方法？
第1类：第1步走1阶，剩下还有n-1阶要走，有f(n-1)种方法。
第2类：第1步走2阶，剩下还有n-2阶要走，有f(n-2)种方法。
就得到了递推式：f(n)=f(n-1)+f(n-2),
2.兔子繁殖
把雌雄各一的一对新兔子放入养殖场中。每只雌兔在出生两个月以后，每月产雌雄各一的一对新兔子。试问第n个月后养殖场*有多少对兔子。
推导出来递推关系f(n)=f(n-1)+f(n-2):
第n个月的兔子由两部分组成，一部分是上个月就有的老兔子f(n-1)，一部分是上个月出生的新兔子f(n-2)(第n-1个月时具有生育能力的兔子数就等于第n-2个月兔子总数
3.骨牌排列
有 2n的一个长方形方格，用一个12的骨牌铺满方格。
分析问题：
当n=1时，只能是一种铺法，铺法总数有示为x1=1。
当n=2时：骨牌可以两个并列竖排，也可以并列横排，再无其他方法，x2=2
当n=3时：骨牌可以全部竖排，也可以认为在方格中已经有一个竖排骨牌，则需要在方格中排列两个横排骨牌（无重复方法），若已经在方格中排列两个横排骨牌，则必须在方格中排列一个竖排骨牌。x3=3；
推出一般规律：对一般的n，要求xn可以这样来考虑，若第一个骨牌是竖排列放置，剩下有n-1个骨牌需要排列，这时排列方法数为xn-1；若第一个骨牌是横排列，整个方格至少有2个骨牌是横排列（1*2骨牌），因此剩下n-2个骨牌需要排列，这是骨牌排列方法数为xn-2。从第一骨牌排列方法考虑，只有这两种可能，
斐波那切数列问题在分析过程中可以将子问题分成两种情况！！（发现斐波那切数列规律的方式）
下面是输入n，输出x1~xn的c++程序：
#include
using namespace std;
int main()
{
int n,i,j,a[101];
cout<<“input n:”; //输入骨牌数
cin>>n;
a[1]=1;a[2]=2;
cout<<“x[1]=”<<a[1]<<endl;
cout<<“x[2]=”<<a[2]<<endl;
for (i=3;i<=n;i++) //递推过程
{
a[i]=a[i-1]+a[i-2];
cout<<“x[”<<i<<"]="<<a[i]<<endl;
}
}
下面是运行程序输入 n=30，输出的结果：
input n: 30
x[1]=1
x[2]=2
x[3]=3
…
x[29]=832040
x[30]=1346269（斐波那契数。）