算法与算法分析_11复杂化计算

算法与算法分析

算法是，对特定问题求解方法和步骤的一种描述，它是有限指令的有限序列，其中每个指令表示一个或多个操作。

算法与程序的比较

• 算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。
• 程序是用某种程序设计语言对算法的具体实现。
• 程序 = 数据结构 + 算法

算法的特性

一个算法必须具备以下五个重要特性：

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

算法设计有正确性（Correctness）、可读性（Readability）、健壮性（Robustness）、高效性（Efficiency）的基本要求。
一个好的算法首先要具备正确性，然后是健壮性，可读性，在几个方面都满足的情况下，主要考虑算法的效率，通过算法的效率高低来评判不同算法的优劣程度。

算法效率分析

算法效率主要从一下两个方面来考虑：

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

时间效率分析
一个算法在计算机上运行所耗费的时间大致可以等于计算机执行一种简单的操作（如赋值、比较、移动等）所需的时间与算法中进行简单操作次数的乘积。
算法运行时间 = 一个简单操作所需的时间 x 简单操作次数 ，
也就是算法中每条语句的执行时间之和

每条语句执行一次所需的时间，一般是随机器而异的，取决于机器的指令性能、速度以及编译的代码质量，是由机器本身软硬件环境决定的，它与算法无关。所以，可以假设执行每条语句所需的时间均为单位时间。 此时对算法的运行时间的讨论就可以转化为讨论改算法中所有语句的执行次数了。

例如：两个n x 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次
	}
1
2
3
4
5
6
7

则上述算法的时间消耗T(n) = 2n³ + 3n² + 2n + 1
注：为了便于比较两个算法的时间效率。我们仅仅比较他们的数量级。

时间复杂度

若有，有某个辅助函数f(n)，使得当n趋近与无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数，计作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度（O是数量级的符号），简称时间复杂度。

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

1. 找出语句频度最大的那条语句作为基本语句
2. 计算基本语句的频度得到问题规模n的某个函数f(n)
3. 取其数量级用符号“O”表示

其中基本语句是指：

• 算法中重复执行次数和算法的执行之间成正比的语句；
• 对算法运行时间的贡献最大
• 执行次数最多

对于复杂的算法，可以将它拆分成几个容易估算的部分，然后用加法法则和乘法法则计算时间复杂度：
a) 加法法则
T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n),g(n)))

b)乘法法则
T(n) = T1(n) x T2(n) = O(f(n)) x O(g(n)) = O(f(n) x g(n))

算法时间效率的比较

可见，常数阶<对数阶<线性阶<线性对数阶<平方阶< …<K方阶<指数阶

空间复杂度

算法所需存储空间的度量，记作： S(n) = O(f(n)) , n为问题的规模。

算法要占据的空间

• 算法本身要占据的空间，输入/输出，指令，常数，变量等
• 算法要使用的辅助空间