算法就是按步就班的解决某个问题的方法。
要让计算机解决一个问题，这个问题的解决方法必须描述成一组精确步骤的序列。
algorithm一词源自公元9世纪的波斯数学家Al-Khowarizmi。

本章内容

• 算法及符号表示法
• 除数算法
• 执行时间和空间的复杂度
• 一些特殊算法的资源分析

3.1引言

算法一组有限的指令集合
确定性、准一性、有限性、输入输出通用性

算法设计

查找大于给定正整数的最小素数 给定n?最小素数p p>n

        static int
        NextPrime( int N )
        {
            int i;
 
            if( N % 2 == 0 )
                N++;
            for( ; ; N += 2 )
            {
                for( i = 3; i * i <= N; i += 2 )
                    if( N % i == 0 )
                        goto ContOuter;  /* Sorry about this! */
                return N;
              ContOuter: ;
            }
        }

习题：P125 1、4 、15

3.3 欧氏算法

求两个整数的最大公约数

Procedure gcd_recurs(a,b)
if a < b then
  swap(a,b)
if b=O then
  return(a)
return(gcd_recur (b,r))
End gcd_recurs

3.4递归算法

能够i调用自身的过程叫做递归过程
包含递归过程的算法叫做递归算法
分而治之（分治法）

Input: n，大于等于O的整数
ouput: n!
Procedure factorial(n)
if n=o then
  return(1)
return(n*factorial(n-1))
end

递归通过数学归纳法进行证明！

机器人一步能走1或2米，走n米一共有多少种走法？

procedure robot_walk(n)
if n=1 or n=2 then
return(n)
return(robot_walk(n-1)＋
robot_walk(n-2))
end robot_walk

Fibonacci级数

1,2,3,5,8,13，…
f₁=1，f₂=2，f_n=f_n-1+f_n-2 （n≥3）

习题：P136 7 、13

3.5 算法复杂度

时间开销,空间开销,算法分析,算法复杂度。（数据结构已讲）
例：
集合x包含n个元素,红/黑，问有多小个x的子集包含至少一个红色的元素?
时间开销：

• 最好情况下的时间
• 最坏情况下的时间
• 平均时间

定义：
f，g函数,定义域{1，2，...}
若存在C₁对所有n满足：| f(n) |≤C₁ l g(n) l
则称f(n)最大以g(n)为阶，f(n)=O(g(n))
若存在C₂对所有n满足：| f(n) |≥ C₂ l g(n) |
则称f(n)最小以g(n)为阶，f(n)= Ω(g(n))

---

lgn log₂n

2n +3lgn <2n+3n=5n2n + 3lgn = O(n)
2n+ 3lgn > 2n2n+3lgn = 2(n)
2n+3lgn = O(n)
习题：P148 7，10,16