算法与算法分析

一  概述

1. 对特定问题求解方法和步骤的一种描述，它是指令的有限序列。其中每个指令表示一个或多个操作
2. 简而言之：算法就是解决问题的方法和步骤
3. 描述：

1. 自然语言：英文，中文
2. 流程图：传统流程图，NS流程图
3. 伪代码：类语言

4. 算法与程序

1. 算法是解决问题的一种方法或一个过程，考虑如何将输入转化成输出，一个问题可以有多种算法
2. 程序是用某种程序语言对算法的具体实现

5. 算法特性：一个算法必须具备的五种特性

1. 有穷性：每一个代码必须在执行有穷步之后结束，且每一步都在有穷的时间内完成
2. 确定性：算法中的每一条指令必须有准确的含义，没有二义性，在任何条件下，只有唯一的执行路径，即对于相同的输入只能得到相同的输出
3. 可行性：算法是可执行的，算法描述的操作可通过已经实现的基本操作执行有限次来实现
4. 输入：算法有零个或多个输入
5. 输出：算法有一个或多个输出

6. 设计要求

1. 正确性：算法满足问题要求，能正确解决问题。在转化为程序后：程序对于精心设计的、典型的、苛刻且带有刁难性的几组输入数据能够得到满足要求的结果
2. 可读性：主要为了易于人的阅读与交流，其次才是为了计算机的执行
3. 健壮性：当输入非法指令时，算法恰当做出相应的反应，处理出错的方法，不应该是中断执行，而应返回一个表示错误或错误性质的值
4. 高效性：运行要求花费尽量少的时间与内存空间

二  算法分析

1. 算法在正确性，可读性，健壮性都满足的前提下，通过算法效率来判断算法的优劣
2. 算法效率的考虑

1. 时间效率：指算法所耗费的时间
2. 空间效率：指算法执行过程中消耗的存储空间
3. 时间效率与空间效率有的时候是矛盾的

3. 算法时间效率的度量依据该算法编制的程序在计算机上的执行所消耗的时间来度量

1. 度量方法：事后统计：将算法实现，测算其时间和空间的开销。缺点：编写程序实现算法需要消耗时间和经历，所得的实验结果也依赖于计算机的软硬件等环境因素，掩盖了算法本身的优劣
2. 度量方法：事前分析：对算法消耗资源的一种估算方法。估算方法：执行的一种简单操作（如：赋值，比较，移动等）所需的时间与操作次数的乘积
3. 算法运行时间 = 每条语句的执行次数 x 该条语句执行一次的时间
4. 语句执行的时间，一般是随机器而异的。取决于机器的指令性能、速度以及编译的代码质量（使用的编译语言，往往高级语言耗费的时间较长）。是由机器本身软硬件环境决定的，它于算法本身无关。所以，我们可以假设每条语句执行所需的时间均为单位时间。此时对时间的讨论可以转化成讨论语句执行的次数，即频率之和
5. 例如：计算俩个n × n 的矩阵

for (i = 0; i < n; i++){  //执行 n+1 次，内循环n次，最后一次判断条件是否成立
    for (j = 0; j < n; j++){  //执行 n*(n+1) 次
        c[i][j] = 0;  //执行 n*n次
        for (k = 0; k < n; k++){  //执行n*n*(n+1)次
        c[i][j] = c[i][j] + a[i][k] * b[k][j];  //执行n*n*n次
        }
    }
}1. for (i = 0; i < n; i++){  //执行 n+1 次，内循环n次，最后一次判断条件是否成立
2. for (j = 0; j < n; j++){  //执行 n*(n+1) 次
3.         c[i][j] = 0;  //执行 n*n次
4. for (k = 0; k < n; k++){  //执行n*n*(n+1)次
5.         c[i][j] = c[i][j] + a[i][k] * b[k][j];  //执行n*n*n次
6.         }
7.     }
8. }

1. 算法中基本语法重复执行的次数是问题规模n的某个函数f(n)，n越大执行时间越长。

1. 分析时间复杂度的基本方法

1. 找出语句频率最大的那条语句作为基本语句
2. 计算基本语句的频度得到问题规模n的函数f(n)
3. 找出数量级使用T(n) = O(n的次数表示)
4. 算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如查找数据是存在：最坏，平均，最好时间复杂度，一般考虑最坏的情况
5. 例：

int i = 1;
while (i <= n){
    i = i * 2;
}
分析：
若循环执行一次：i = 2
若循环执行二次：i = 2^2
若循环执行三次：i = 2^3
……
若循环执行x次：i = 2^x
执行判断条件 i = 2^x <= n  
即 x <= log以2为底的n
则 T(n) = O(log以2为底的n)

1. 对于复杂的算法，可以将它分成几个容易估计的部分，然后利用O(n)的乘法与加法法则进行计算

1. 算法时间效率的比较
   
   
2. 空间复杂度

1. 算法所需要的存储空间的度量，S(n) = O(f(n))
2. 算法本身要占的空间，输入/输出，指令，常数，变量等
3. 算法需要的辅助空间
4. 例：将一维数组a中的n个数逆序存放到原数组

算法1：
for (i = 0; i < n / 2; i++){
    t = a[i];
    a[i] = a[n - i -1];
    a[n - i - 1] = t;
}
即 t 为辅助空间  S(n) = O(1)原地工作
算法2：
for (i = 0; i < n; i++){
    b[i] = a[n - i -1];
}
for (i = 0; i < n; i++){
    a[i] = b[i];
}
需要提供b[n]的空间  S(n) = O(n)