基本概念

• 算法是问题求解步骤的描述，指令的有限序列。

特性

1. 有穷性：步数有穷，且每一步时间有穷。
2. 确定性：相同输入有相同输出。
3. 可行性：操作都可以通过已经实现的基本运算执行有限次实现。
4. 输入：有 ≥0 个输入。
5. 输出：有至少一个输出。

设计要求

1. 正确性：正确地求解问题。
2. 可读性：记得写注释！
3. 健壮性：非法数据的高抽象层次处理。
4. 效率：算法执行的时间。
5. 存储量需求：执行过程中所需的最大存储空间。

时间复杂度

• 频度：该语句在算法中被重复执行的次数。
• 频度之和为 ，其中 为问题规模。

加法规则

• 即取最大值，例如

乘法规则

(★) 例题#1 - 求出下列算法的时间复杂度

• Example #1
• Example #2
• Example #3

1
2i = 0, k = 1;
3while(i < n){
4k = k + 10 * i;
5i++;
6}
7

1
2i = 0;
3while(i * i * i <= n){
4i++;
5}
6

1
2i = 0;
3while(i <= n){
4i = i * 2;
5}
6

空间复杂度

• 辅助空间：对数据进行加个的工作单元和存储。
• 算法原地工作：不需要任何额外的辅助空间。