算法设计与分析

算法的基本概念

 

【基础知识点】

1、基本概念：算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

2、算法的特性：有穷性、确定性、可行性、输入、输出。

3、“好”算法要求：正确性、健壮性、高效性。

4、算法表示

算法表示	优点	缺点
自然语言	容易理解	二义性，冗长
流程图	直观易懂	严密性不如程序设计语言，灵活性不如自然语 言
程 序 设 计 语言	计算机直接运 行	抽象性差，拘泥细节忽视正确性，需要掌握编 程
伪代码	简明扼要

算法分析基础

【基础知识点】

1、算法复杂性：时间复杂性、空间复杂性。

2、渐进符号

1）Ο记号。给出一个函数的渐进上界。给定一个函数g(n)，Ο(g(n))表示为一个函数集合｛f(n):

存在正常数c和n0，使得对所有的n≥n0，有0≤f(n)≤cg(n)｝。

2）Ω记号。给出一个函数的渐进下界。给定一个函数g(n)，Ο(g(n))表示为一个函数集合｛f(n):

存在正常数c和n0，使得对所有的n≥n0，有0≤cg(n)≤f(n)｝。

3）Θ记号。给出一个函数的渐进上界和下界，即渐进确界。给定一个函数g(n)，Ο(g(n))表示为一个函数集合｛f(n):存在正常数C1、C2和n0，使得对所有的n≥n0，有0≤C1g(n)≤f(n)≤C2g(n)｝。

由上述定义可知，f(n)＝Θ(g(n))当且仅当 f(n)＝Ο(g(n))和 f(n)＝Ω(g(n))。

3、递归式

1）展开法

2）代换法

3）递归树法

4）主方法

分治法

【基础知识点】

1、递归的概念

2、分治法思想：分解、求解、合并

3、分治法实例：归并排序

动态规划法

 

【基础知识点】

1、基本思想

1）找出最优解的性质，并刻画其结构特征

2）递归定义最优解的值

3）自底向上算出最优解

4）构造最优解

2、实例：0-1背包问题

贪心法

【基础知识点】

1、基本思想

2、实例：活动选择问题、背包问题

回溯法

 

【基础知识点】

1、解空间

2、基本思想

3、算法框架：非递归、递归

4、实例：0-1背包问题

分支限界法

 

【基础知识点】

1、队列式（FIFO）分支限界法

2、优先队列式分支限界法

概率算法

 

【基础知识点】

1、数值概率算法

2、蒙特卡罗（Monte Carlo）算法

3、拉斯维加斯（Las Vegas）算法

4、舍伍德（Sherwood）算法

近似算法

 

【基础知识点】

1、性能标准：算法的时间复杂度、解的近似程度

2、实例：定点覆盖问题、TSP问题、子集和数问题

NP完全性理论

【基础知识点】

1、P 类问题和 NP 类问题

2、NP完全问题

3、典型的 NP完全问题

练习题

●在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用（ 1 ）算法设 策略，以深度优先的方法是搜索解空间，则采用（ 2 ）算法设计策略。

（1）A.分治               B.动态规则                 C.贪心                D.回溯

（2）A.动态规划                B.贪心                         C.回溯                D.分治限界

解析： 动态规划算法总体思想：如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法从根开始计算，到找到位于某个节点的解，回溯法（深度优先搜索）作为最基本的搜索算法，其采用了一种“一直向下走，走不通就掉头”的思想（体会“回溯”二字），相当于采用了先根遍历的方法来构造搜索树。

参考答案：（1）B （2）C

●考虑下述背包问题的实例。有 5 件物品，背包容量为 100，每件物品的价值和重量如下所示， 并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中，     则采用了（  3  ）设计策略。考虑 0/1 背包问题(每件物品或者全部装入背包或者不装入背包)和部分背包问题(物品可以部分装入背包)，求解该实例得到的最大价值分别为（ 4 ）。

物品编号	价值	重量
1	50	5
2	200	25
3	180	30
4	225	45
5	200	50

 

解析：本题考查贪心算法和背包问题的知识点。

贪心算法(又称贪婪算法)是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

采用0／1背包考虑该问题时，只能放入1、2、3号物品，故总价值为430，采用部分背包可以将物品拆分，故放入1、2、3号物品后还可以将编号4的物品部分的装入，使得背包容量尽量的满，故总容量为630。

参考答案：（3）B （4）C

●给定n个整数构成的数组A={a1，a2，……，an}和整数x，判断A中是否存在两个元素ai 和aj，是的ai+aj=x。为了求解问题，首先用归并排序算法对数组 A 进行从大到小排序；然后判断是否存在ai+aj=x，具体的方法如下列伪代码所示。则求解该问题时排序算法应用了（ 5  ）算法设计策略，整个算法的时间复杂度为（ 6 ）。

i=1;j=n

   While i＜j

      If ai+aj=x return true

      Else if ai+aj＞x

        J--;

      Else

       I++;

       Return false;

（5）A．分治                     B．贪心                       C．动态规划            D．回溯

（6）A．O(n)                      B．O(nlgn)         C．O(n2)                     D．O(nlg2n)

[解析] 分治算法的基本思想是将一个规模为 N 的问题分解为K 个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。

参考答案：（5）A （6）B