算法简介1. 什么是算法？在有限步骤内求解问题所使用的一组定义明确的规则。
算法A 解问题 P
（1）把问题 P 的任何实例作为算法 A 的输入；
（2）每步计算是确定性的，即每步的计算依赖于前一步的计算结果和输入数据；
（3）能够在有限步停机；
（4）输出该实例的正确的解。
2. 算法的性质算法是指解决问题的一种方法或一个过程。 算法是若干指令的有穷序列，满足性质： (1)输入：有外部提供的量作为算法的输入。 (2)输出：算法产生至少一个量作为输出。 (3)确定性：组成算法的每条指令是清晰，无歧义的。 (4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。 (5)可行性：算法中的操作都是可以通过已经实现的基本运算执行有限次来实现的
3. 什么是程序？是算法用某种程序设计语言的具体实现，它可以不满足算法的“有限性”。 如：操作系统
4. 算法与程序的关系算法是程序的灵魂，程序是算法的躯体
5. 算法复杂度分析（1）时间复杂度随着输入规模 n 的增加，算法运行时间的增长趋势。这种分析有助于评估算法的效率，并且对于选择最佳算法来解决问题非常有用。
举例：查找问题 查找问题是一类问题，其实每个查找具体问题就是一个实例。
（2）空间复杂度衡量算法在运行过程中所需内存空间大小的一个指标。它描述了算法所占用的存储空间与输入数据规模之间的关系。
时间复杂度 是对算法效率的度量 算法运算次数与问题实例规模的关系 在规模相同的情况下，不同实例，运算次数可能不同
6. 时间复杂度分析举例（1）查找问题 最好的情况 1次 最坏的情况 n次 平均情况下的运算次数
(p(n+1))/2+(1-p)n P=1/2 3n/4
7. 函数的渐近的界
picture 78. 常见的复杂性函数 （1）中小规模数据 （2）中等规模数据