动态规划，基本上就是说：

你追一个MM的时候，需要对该MM身边的各闺中密友都好，这样你追MM这个问题就分解为对其MM朋友的问题，只有把这些问题都解决了，最终你才能追到MM。

该方法适用于聪明的MM，懂得“看一个人，不是看他如何对你，而是看他如何对他人。”的道理，并且对付这样的MM总能得到最优解。

该方法的缺点是开销较大，因为每个子问题都要好好对待。。。。

////////////////////////////////////////////////////////////////////

贪心法，基本上就是：

你追一个MM的时候，从相识到相知，每次都采用最aggressive的方式，进攻进攻再进攻！从不采用迂回战术或是欲擒故纵之法！目标是以最快的速度确立两人关系。

该法优点是代价小，速度快，但缺点是不是每次都能得到最优解。。。。。

////////////////////////////////////////////////////////////////////

回溯算法，基本上就是：

追一个MM，但也许你还是情窦初开的新手，不知道如何才能讨得MM的欢心，于是你只好一条路一条路的试，MM不开心了，你就回溯回去换另一种方式。当然其间你也许会从某些途径得到一些经验，能够判断哪些路径不好，会剪枝（这就是分支估界了）。你也可以随机选择一些路径来实施，说不定能立杆见影（这就是回溯的优化了）但总的来说，你都需要一场持久战。。。。

该算法一般也能得到最优解，因为大多数MM会感动滴！！但其缺点是开销大！除非你是非要谈一场恋爱不可，否则不推荐使用。特别是你可能还有许多其他的事情要做，比如学习，比如事业。。。。

////////////////////////////////////////////////////////////////////

…… …… 余下全文

算法分析与设计

学习总结

题目：算法分析与设计学习总结

学 院 信息科学与工程学院 专 业 届 次 学生姓名 学 号

二○一三年一月十五日

算法分析与设计学习总结

本学期通过学习算法分析与设计课程，了解到：算法是一系列解决问题的清晰指令，代表着用系统的方法描述解决问题的策略机制。算法能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法设计与分析是计算机科学与技术的一个核心问题。

设计的算法要具有以下的特征才能有效的完成设计要求，算法的特征有：（1）有穷性。算法在执行有限步后必须终止。（2）确定性。算法的每一个步骤必须有确切的定义。（3）输入。一个算法有0个或多个输入，作为算法开始执行前的初始值，或初始状态。（4）输出。一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。（5）可行性。在有限时间内完成计算过程。

算法设计的整个过程，可以包含对问题需求的说明、数学模型的拟制、算法的详细设计、算法的正确性验证、算法的实现、算法分析、程序测试和文档资料的编制。算法可大致分为基本算法、数据结构的算法、数论与 代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法和并行算法。

经典的算法主要有：

1、 穷举搜索法

…… …… 余下全文

算法设计与分析总结

一、算法引论

算法：通常人们将算法定义为一个有穷的指令集，这些指令为解决某一特定的任务规定了一个运算序列。

什么是算法?

计算机来解决的某一类问题的方法或步骤。

算法是程序的核心。

算法的两个要素：

算法是由操作与控制结构两个要素组成。

（1）操作

①算术运算：加、减、乘、除等。

②关系运算：大于、大于等于、小于、小于等于、等于、不等于等。

③逻辑运算：与、或、非等。

④数据传送：输入、输出、赋值等。

（2）控制结构

各操作之间的执行顺序：

顺序结构、选择结构、循环结构，称为算法的三种基本结构

一个算法应当具有以下特性：

1、输入。一个算法必须有0个或多个输入。它们是算法开始运算前给予算法的量。

2、输出。一个算法应有一个或多个输出，输出量是算法计算的结果。

3、确定性。算法的每一步都应确切地、无歧义的定义，对于每一种情况，需要执行的动作都应严格的，清晰的规定。

4、有穷性。一个算法无论在什么情况下都应在执行有穷步后结束。

5、有效性。算法中每一条运算都必须是足够基本的。原则上都能够被精确的执行。

6、一个问题可以有多个解决的算法。

程序可以不满足条件4。

计算机程序是算法的实例，是算法采用编程语言的具体实现 。

算法的分类：

（1）数值计算算法

（2）非数值计算算法

算法的表示：

1、自然语言

2、传统流程图

3、N-S流程图

4、伪代码

5、计算机语言

计算机程序设计中有两个核心目标：

1、算法必须是易于理解，编码和调试的

2、设计的算法能够最有效的使用计算机的资源。

目标1是软件工程的概念 ；

目标2是数据结构和算法设计的概念 ；

判断一个算法的优劣，主要有以下标准：

1、正确性：要求算法能够正确的执行预先规定的功能和性能要求。

2、可使用性：要求算法能够很方便的使用。

…… …… 余下全文

第一章 概述

算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。 算法的特征：

可终止性：算法必须在有限时间内终止；

正确性：算法必须正确描述问题的求解过程；

可行性：算法必须是可实施的；

算法可以有0个或0个以上的输入；

算法必须有1个或1个以上的输出。

算法与程序的关系：

区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束；

程序可以没有输出,而算法则必须有输出；

算法是面向问题求解的过程描述，程序则是算法的实现。

联系：程序是算法用某种程序设计语言的具体实现；

程序可以不满足算法的有限性性质。

算法描述方式：自然语言，流程图，伪代码，高级语言。

算法复杂性分析：

算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。

算法复杂性度量：

期望反映算法本身性能，与环境无关。

理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响）。

一般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单 位的开销作为标准。

算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F(N, I, A)。

第二章 递归与分治

分治法的基本思想：

求解问题算法的复杂性一般都与问题规模相关，问题规模越小越容易处理。

分治法的基本思想是，将一个难以直接解决的大问题，分解为规模较小的相同子问题，直至这些子问题容易直接求解，并且可以利用这些子问题的解求出原问题的解。各个击破，分而治之。

分治法产生的子问题一般是原问题的较小模式，这就为使用递归技术提供了方便。递归是分治法中最常用的技术。

使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。

分治法所能解决的问题一般具有以下几个特征：

…… …… 余下全文

第一章：

1.         算法定义：算法是若干指令的有穷序列，满足性质：

(1)输入：有外部提供的量作为算法的输入。

(2)输出：算法产生至少一个量作为输出。

(3)确定性：组成算法的每条指令是清晰，无歧义的。

(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。

2.         程序定义：程序是算法用某种程序设计语言的具体实现。可以不满足算法的性质(4)。

3.         算法复杂性分为时间复杂性和空间复杂性。

4.         可操作性最好且最有使用价值的是最坏情况下的时间复杂性。

5.         O(n)定义：存在正的常数C和自然数N₀，当N>=N₀时有f(N)<=Cg(N),则称函数f(N)当N充分大时有上界，记作f(N)=O(g(n)).

6.         ?(n)定义：存在正的常数C和自然数N₀，当N>=N₀时有f(N)>=Cg(N),则称函数f(N)当N充分大时有上界，记作f(N)=?(g(n)).

7.         (n)定义:当f(n)=O(g(n))且f(N)=?(g(n))，记作f(N)=(g(n))，称为同阶。

…… …… 余下全文

第一章 绪论

1、重要特性

1.输入

2.输出

3.有穷性

4.确定性

5.可行性

2、描述算法的方法

1.自然语言：优点是直观易懂，缺点是容易出现二义性

2.流程图：优点是直观易懂，缺点是严密性不如程序设计语言，灵活性不如自然语言

3.程序设计语言：优点是计算机直接运行，缺点是抽象性差

4.伪代码：

3、递归算法分析

1.猜测技术

2.扩展递归技术

3.通用分治递归推式

第二章 NP完全理论

第三章 蛮力法

3.1 蛮力法的设计思想

蛮力法依赖的基本技术——扫描技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解;

关键——依次处理所有元素。

3.2 查找问题中的蛮力法

3.2.1 顺序查找O(n)

3.2.2串匹配问题

BF O(n*m)

BMP O(n+m)

BM O(n*m)

3.3 排序问题中的蛮力法

3.3.1 选择排序O(n²)

3.3.2 起泡排序O(n²)

3.4 组合问题中的蛮力法

3.4.1 生成排列对象O(n!)

3.4.2 生成子集O(2ⁿ)

3.4.3 0/1背包问题O(2ⁿ)

3.4.4 任务分配问题O(n!)

3.5 图问题中的蛮力法

3.5.1 哈密顿回路问题O(n!)

3.5.2 TSP问题O(n!)

3.6 几何问题中的蛮力法

3.6.1 最近对问题O(n²)

3.6.2 凸包问题O(n³)

3.7 实验项目——串匹配问题

第四章 分治法

4.1 分治法的设计思想

设计思想：将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。

…… …… 余下全文

简答：

1.  算法定义：

算法是一个满足下列条件的计算：

①   有穷性/终止性：有限步内必须停止。/* 好算法/坏算法 */

②   确定性：每一步都是严格定义和确定的动作。 /* 要严格算法语言 */

③   能行性：每一个动作都能够被精确地机械执行。

④   输入：有一个满足给定约束条件的输入。

⑤   输出：满足给定约束条件的结果。

2.  常用算法及其特点：

递归分治法，贪心算法，动态规划，回溯法等。

3.  递归分治法：

基本思想：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

4.  动态规划法：

1）适用条件：当一个优化问题可分为多个子问题，子问题的解被重复使用。具有最优子结构和重叠子问题

2）基本思想：求解每个子问题仅一次，并保存其结果，以后用到时直接存取，不重复计算，节省计算时间。

3）解题步骤：

      ① 分析优化解的结构

      ② 递归地定义最优解的代价

      ③ 自底向上地计算优化解的代价保存之，并获取构造最优解的信息

      ④ 根据构造最优解的信息构造优化解

   4）与递归分治法的区别：动态规划法自底向上，递归分治法自顶向下

5.  贪心算法：

  1）基本思想

    ·求解最优化问题的算法包含一些列步骤

…… …… 余下全文