跳到主要内容

算法分析

算法的特性​

Algorithm 是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。此外，一个算法还具有下列 5 个重要特性。

  1. 有穷性：一个算法必须总是（对任何）在执行有穷步骤之后结束，且每一步都可在有穷时间内完成。
  2. 确定性：算法中的每一条指令必须有确切的含义，理解时不会产生二义性。并且在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
  3. 可行性：一个算法是可行的，即算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
  4. 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。
  5. 输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。

算法的复杂度​

算法的时间复杂度分析：主要是分析算法的运行时间，即算法执行所需的基本操作数（具体运行时间是无法直接衡量的）。不同规模的输入所需要的基本操作数是不相同的。在算法分析中，可以建立以输入规模 n 为自变量的函数 T(n) 来表示算法的时间复杂度。

即便对于 相同的输入规模，数据分布不相同也影响了算法执行路径的不同，因此所需要的执行时间也不同，根据不同的输入，将算法的时间复杂度分为 3 中情况：最佳情况、最坏情况、平均情况。

渐进符号​

以输入规模 n 为自变量建立的时间复杂度实际上还是较复杂的，例如 an2+bn+can^2 + bn + c，不仅与输入规模相关，还与系数 a、b、c 有关。此时可以 对该函数做进一步的抽象，仅考虑运行时间的增长率或称为增长的量级，如忽略上式中高阶和低阶项的系数，仅考虑 n2n^2 。当输入规模大到只有与运行时间的增长量级有关时，就是在研究算法的渐进效率。也就是说，从极限角度看，只关心算法运行时间如何随着输入规模的无限增长而增长。

常见的时间复杂度​

  1. 常数级
 int sum = 0, n = 100;
 sum = (1+n)*n/2;
 printf("%d",sum);
  1. 线性级
int i;
for(i = 0;i<n;i++){
	...
}

  1. 对数级
 int count = 1;
 while(count<n){ // 假设 n 为 17 ，会执行 log2n 次
 	count = count * 2;
 }
  1. 平方级

 int i,j;
 for(i = 0;i<n;i++){
 	for(j=0;j<n;j++){
 		...
 	}
 }

  1. 线性对数

渐进符号​

渐进符号 O 表示一个渐进变化程度，实际变化必须小于等于 O 括号内的渐进变化程度。

递归​

递归是指 子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的常用方法。递归有两个基本要素：边界条件，即确定递归到何时终止，也称为递归出口；递归模式，即大问题是如何分解为小问题的，也称为递归体。

阶乘的函数可递归地定义为：

n!={1,n=0,1n(n−1)!,n>1 n! = \begin{cases} 1 & ,n=0,1\\ n(n-1)! & ,n>1\\ \end{cases}

阶乘函数的自变量 n 的定义域是非负整数。递归式的第一式给出了这个函数的一个初始值，是递归的边界条件。递归式的第二式使用较小的自变量的函数值来表示较大自变量的函数值得方式来定义 n 的阶乘，是递归体。n! 可以递归地计算如下：

int Factorial(int num){
	int(sum == 1||sum==0){
	  return 1
	}
	if(num >0){
		return sum * Factorial(num-1);
	}
}

递归算法的时间复杂度分析方法：将递归式中等式右边的项根据递归式进行替换，称为展开。展开后的项被再次展开，如此下去，直到得到一个求和表达式，得到结果。