一、
1.算法的属性：
1.输入。2.输出。3.正确性。4.有穷性（有限步数）。5.有效性（有限时间内正确执行每个步骤）。6.泛化性。
2.指定算法：
可用 语言 or 伪代码 来描述
二、三类问题
1.搜索问题：
(1) 线性搜索：
从头到尾一个一个检查。
(2) 二分搜索：（假设排列是按递增顺序的）
（找到：返回位置；未找到：返回0；）
2.排序问题：
（二分，插入，冒泡，选择，合并，快速，锦标赛）
（1）冒泡排序
（2）插入排序：
从第二个元素开始。将第二个元素与第一个元素进行比较，如果不大于第一个元素，则将其放第一个元素之前。
（3）选择排序：
首先找出列表中最小元素。把这个元素移到前面。然后找出剩余元素里的最小元素并且把它放到第二个位置。重复这个过程，直到整个列表都已经排好序为止（直到只剩下1个元素未选择）。（别忘了交换位置）
3.最优化问题：（通常可用贪心(贪婪)算法来解决）
贪心算法：在每一步做出“最佳”选择。
但有时贪心算法并不是整个问题的最优解（只是很多情况下由贪心算法得出的都是最优解）
（1）例1：用25美分，10美分和1美分（但是没5美分）硬币找出 兑换：
a）76美分, b) 69美分 对于 a、b , 贪心算法是否都为最优解？
（使用硬币数量尽可能少）
（2）例2：安排会议
对于n个讲座，用蛮力算法：O(n^2·2^n)
用贪婪算法：选择结束时间最早的会议
三、函数的增长率
1.大O表示
(1)存在常数C和k，当x>k时，有 |f(x)|<=C|g(x)| : f(x)是g(x)的大O表示（f=O(g)），或g是f的上限。
(2)几种常见的复杂度比较：
幂指>阶乘>指数>幂（n）>O(nlogn)>幂（根号n）>O(logn)>常数(O(1))（指数小于1）,其中，对数：O(nlogn)>O(logn)
例：
2.大Ω表示
(1)存在常数C和k，当x>k时，有 |f(x)|>=C|g(x)| : f(x)是g(x)的大Ω表示。（下界）（下界的阶越高，越精确）
3.大θ表示（来自1.和2.）
四、时间复杂度 (以下为最坏时间复杂度)
1.线性搜索：O(n)。
2.二分搜索：O(logn)。
3.冒泡排序：O(n^2)
4.插入排序：O(n^2)
例题：
