算法设计与分析（一） 蛮力法

一、概述 蛮力法是一种简单直接地解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。也可以用“just do it！”来描述蛮力法的策略。一般来说蛮力策略也常常是最容易实现的方法。 二、优缺点 虽然巧妙和高效的算法很少来自于蛮力法，但它在算法设计策略中仍然具有重要地位. 1.蛮力法适应能力强，是唯一一种几乎什么问题都能解决的一般性方法。 2.蛮力法一般容易实现,在问题规模不大的情况下，蛮力法能够快速给出一种可接受速度下的求解方法. 3.虽然通常情况下蛮力法效率很低，但可以作为衡量同类问题更高效算法的准绳。

排序问题 问题：给定一个可排序的n个元素序列（数字、字符或字符串），对它们按照非降序方式重新排列。 解决问题的步骤 1、理解问题 2、选择策略 3、算法设计 4、正确性证明 5、算法分析 6、程序设计

思想：首先扫描整个序列，找到其中一个最小元素，然后和第一个元素交换，将最小元素归位。然后从第二个元素开始扫描序列，找到后n-1个元素中的一个最小元素，然后和第二个元素交换，将第二小元素归位。进行n-1遍扫描之后，排序完成。(选择排序)

流程图或伪代码： 算法 selectSort(A[n]) //用选择法对给定数组排序 //输入：一个可排序数组A[0~n-1] //输出：升序排序的数组A[0~n-1]

效率分析 输入规模：序列元素个数n 基本操作：比较次数A[j] < A[min] 影响基本操作执行次数的因素：n 建立基本操作求和表达式 利用求和公式分析算法时间复杂性 T(n) = （n - 1 )+ （n - 2）+（n - 3）+ …. + 1 = [n*(n-1) ] / 2； O( n^2 )

冒泡排序 思想：扫描整个序列，比较相邻元素，如果它们是逆序的话就交换位置，重复n-1次扫描，排序完成。第i遍需要扫描的元素为0～n-1-i。

算法 bubbleSort(A[n]) //用冒泡法对给定数组排序 //输入：一个可排序数组A[0..n-1] //输出：升序排序的数组A[0..n-1]

效率分析 T(n) = （n - 1 )+ （n - 2）+（n - 3）+ …. + 1 = [n*(n-1) ] / 2； O( n^2 )

顺序查找 问题：查找给定序列中固定值—查找键。

思想：查找键与表中元素从头至尾逐个比较。 结果：找到 或 失败 限位器：把查找键添加到列表末尾—— 一定成功，避免每次循环时对检查是否越界（边界检查）

最好效率：T(n) = 1 最差效率：T(n) = n + 1 ;

字符串匹配 问题：给定一个n个字符组成的串，称为文本，一个m（m≤n）个字符组成的串称为模式，从文本中寻找匹配模式的子串。

思想：将模式对准文本的前m个字符，然后从左到右匹配每一对相应的字符，若遇到一对不匹配字符，模式向右移一位，重新开始匹配；若m对字符全部匹配，算法可以停止。注意，在文本中，最后一轮子串匹配的起始位置是n-m（假设文本的下标从0到n-1）

流程图或伪代码 算法 bruteForceStringMatch(T[0..n-1],P[0..m-1]) //蛮力字符串匹配算法实现 //输入1：一个n个字符的数组T[0..n-1]代表一段文本 //输入2：一个m个字符的数组P[0..m-1]代表一个模式 //输出：若查找成功，返回文本第一个匹配子串中的第一个字符的位置，否则返回-1