1-4 算法（2）

算法分析

我们在分析算法时主要考虑算法的效率

• 时间效率：算法执行所耗费的时间
• 空间效率：算法执行所消耗的存储空间

注意：时间效率和空间效率有时是互相矛盾的

算法时间效率度量

定义：用该算法所编制的程序在计算机上所消耗的时间来度量算法效率

两种度量方法：

• 事后统计：将算法实现、测算出时间和空间的开销。 缺点：会受编程条件、硬件的限制
• 事前分析：对算法所消耗资源进行估算

算法运行时间=执行一个简单操作所需时间 x 该语句所执行一次所需时间

                   $=\\Sigma每条语句的执行次数 * 该语句执行一次所需时间$

注意：因为执行一个语句的时间根据机器性能、代码质量有关，所以我们假设执行每条语句所需时间为单位时间。此时对算法的运行时间讨论就可变为讨论该算法中所有语句的执行次数

E.x 两个n*n矩阵相乘的算法可描述为

for(i = 1;i <= n;i++) { //执行n+1次
	for(j = 1;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次
		}
	}
}

所耗时间为每条语句频度总和：

$T(n)=2n^3+3n^2+2n+1$