最直接解决问题的方法：蛮力a算法，详尽的寻找所有解决方案
- Selection sort
- String matching
- Closest pair
- Exhaustive search for combinatorial solutions
- Graph traversal
优缺点
- 简单，易于编程，适用范围广。
- 小任务的标准方法。
- 一些问题的合理算法。
- 一般来说效率低下——无法很好地扩展。
- 使用蛮力原型，或者当已知输入仍然很小的时候。
问题类型:
- 组合决策或优化问题
- 搜索具有特定属性的元素
- 定义域呈指数增长，例如所有排列
蛮力方法-生成和测试:
- 系统地构建所有可能的解决方案
- 评估每一个项目，记录迄今为止最好的项目
- 当所有可能的解决方案都被检查过之后，返回最好的解决方案
4.1 Properties of Sorting Algorithms-5
- in-place if it does not require additional memory except, perhaps, for a few units of memory是否使用多余的空间
- stable if it preserves the relative order of elements with identical keys 对相同的元素是否保持原有的空间顺序
- input-insensitive if its running time is fairly independent of input properties other than size是否其运行时间只与输入值的大小有关
4.2 Selection Sort-5
5-3
Selection Sort总结
1.时间复杂度为Θ(n^2)
2.选择排序是对大记录的小集合进行排序的好算法
3.Selection Sort不是stable的，是in-place和Input-insensitive的
4.3 Brute Force String Matching
5-13 p是要找的单词，t是被找的文本
5-19 对每n-m+1位置进行m次对比，复杂度为O(m*n)
-
步骤
1.在0到n-m中找单词，n为text的长度，m为单词p长度（j是p中的位置，i是t中单词的开头，i+j是t中单个字母的位置）
2.利用t中的i找到与p首字母j相同的位置，利用p的j和t中的i+j来对比首字母后面的字符是否相同
String Matching总结
最差时间复杂度为O(mn)，平均时间复杂度为O(n)
4.4 Brute Force Geometric
Algorithms: Closest Pair
5-23
Closest Pair总结
最差时间复杂度为Θ(n^2)，week6中有更好的解决方法，复杂度为Θ(n log n)
4.5 recursion (left) or iteration (right)
例1: Factorial
6-3
例2:Fibonacci Numbers
1 1 2 3 5 8 13 21 34 55
6-4 basic operation：addition 复杂度：2^n
6-5 时间复杂度都为n
例3: Tower Of Hanoi:Recursive Algorithm
6-12
问题4: Coin Change Problem
问：4元有几种分法
分为两种，有两元和没有两元。有两元认为，剩下币种的总和为2元；没有两元认为，剩下币种的总和为4元.
6-16
6-17/19
- 有三种Base Cases
amount = 0: there is one way (using no coins)，是一种划分方法
amount < 0: there are no ways to make this，方法不成立
denominations = ∅ (and amount > 0): there are no ways to make this，方法不成立
总结
时间复杂度为Θ(2^n)，在week10中，使用memoing or dynamic programming会有更优的时间复杂度
