《计算机算法设计与分析》笔记

第一章 算法概述

1.1算法性质：

输入、输出、确定性、有限性

1.2时间复杂度

1. 上界记号O：如果存在正的常数C和自然数N0，使得当N≧N0时有f(N)≦Cg(N)，则f(N)有上界函数g(N)，记为f(N)= O(g(N))。

2. 同阶记号θ：f(N)=θ(g(N))表示f(N)和g(N)同阶 。

3. 下界记号Ω：如果存在正的常数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：大整数的乘法