本章介绍ACM算法的时间效率问题。 tips：服务器：运算2千万次达到1秒（2*10^7次->1s）

一、例题导入

最大公因数(GCD)：

1.欧几里得辗转相除法（被除数和除数得到余数，取出余数，把之前的除数除以余数，再得到余数。m/n=r1,n/r1=r2,r1/r2=r3……不停辗转（显然n>r1>r2……>r3）.） 每辗转一次，最大公因数是不变的。m=kn+r1,r1=m-kn.显然m,n的最大公因数=n，r1的最大公因数。一直辗转下去直到，余数=0，返回被除数。 （求逆元的时候也可以用到这个方法）

伪代码如下：

• Step 1：if n=0 return the value of m otherwise proceed to Step2
• Step 2:r=m%n
• Step 3:m<-n,n<-r,Go to step 1:m,n,r1,r2……rk,0 (m,n>r1>r2>……>rk>0).rk=GCD(m,n)=GCD(n,r1)=……

欧几里得法复杂度：大概log的n为底的（根号5+1）

2.式除法复杂度：O（n）

t=min(m,n)
while（m%t||n%t）
{	t--;
}
cout<<t<<endl;

3.方法三

• Step 1:Find the prime factors of m;
• Step 2:Find the prime factors of n;
• Step 3:Find the common factors(s)
  • p1<=p2<=p3<=p4
• GCD(m,n)=p1 * p2* p3* p4

分解出各个因子： 把m表示为：m=p1^r1 * p2^r2 * p3^r3……pk^rk

把n表示为：n=p1^s1 * p2^s2 * p3^s3……pk^sk

好好思考一下为什么下面这堆就是GCD,LCM

• m，n的最大公因数GCD=p1^min(r1,s1) * p2^min(r2,s2)……pk^min(rk,sk)
• m，n的最小公倍数LCM=p1^max(r1,s1) * p2^max(r2,s2)……pk^max(rk,sk)
• 可以发现GCD*LCM= m * n

复杂度：O（n²）

二、时间复杂度考虑方向

1.关注问题的输入规模。

所谓规模就是影响一个程序运行时间最大的那个部分。例如上述例题，时间复杂度最依赖的值就是m,n中的最小值。再例如排序的规模，最影响时间的就是需要排序的数的个数。还有算法的选用也是影响时间的（比如用米热测试（大数的素数计算方法，在本章末补充）来计算是否是素数）。还有不同的操作系统同样也会影响。

2.程序中最多的基本操作的次数。

比如例题中求最大公因数，最多的基本操作就是取余。基本操作次数越少，时间复杂度越低

3.关注随着n的增长。

关注随着n的增长，程序的增长姿势。是平方还是线性还是指数还是对数增长。

4.找最坏，平均，最好

先考虑最坏的情况，再考虑平均情况(与最坏情况是由关联的，基本成倍数关系)，以此来考虑复杂度

考虑顺序：

1. 输入规模
2. 基本操作
3. 找最坏，平均，最好（可能有时候没有差别）
4. 计算表达式
5. 结论

三、描述时间复杂度的符号

1. O表示上限.t(n)∈O(g(n))。t(n)在图像上都在g(n)下方
2. Ω表示下线.
3. θ表示等阶（有时候表示成O）。t(n)∈θ(g(n))等价于c1 * g（n)∈t(n)∈c2 * g(n)，并且也满足m1 * t（n)∈g(n)∈m2 * t(n) (c1,c2,m1,m2都是常数)

ps:一般情况下，(logn)k <= n^r (r>0),n^k <= a^n(a>1)

n^3……n^k(p问题)—-(鸿沟)—-(np问题)2^n n!

四、具体用例

1.包含n个元素的一维数组进行比较，看看有没有相等的数。

输入规模：n
基本操作：比较,if(a[i-1]==a[i])
最坏的情况：每个都比过最后一次才找到相等的
复杂度表达式：C（n，2）=n*(n-1)/2（从n个中找所有两个组合进行比较）
结论：n*(n-1)/2∈θ(n²)

2.自我树

自我树定义是d(n)=n+各个位的和。例如762.d(762)=762+7+6+2.（测试用例n<10000）.输入一堆数字，找出是自我树的

• 输入规模：n=10^4

• 基本操作：d(n)

  for(i=1;i<10000;++i){ for(j=1;j<i;++j){//肯定要在比i小的数j中，才可能出现d(j)=i if(d(j)==i)break;//比i大的数，求d(k)肯定>i。但是这种办法并不是最优化的，反而还是超时 } if(j==i)printf(“%d\n”,i); }

• 观察上述代码的复杂度。
  • i=1,需要进行的基本操作次数=0.
  • i=2,需要进行的基本操作次数=1.
  • i=3,需要进行的基本操作次数=2.
  • ……
  • i=n,需要进行的基本操作次数=n-1.
• 因此上述方法的时间复杂度是n*(n-1)/2=O(n^2),也就是θ(n^2)
• 当n=10^4.肯定爆炸了啊。超过1s

现在分析如何优化：

方法一：

• d(n)=n+n1+n2+n3+n4<=n+36（各个位置的和最大就是36，eg：全是9的时候）
• 所以在遍历d(j)的时候j的循环体应该改成for(j=i-40;j<i;j–)或者for(j=i-36;j<i;j–)
• 再次考虑复杂度：
  • i=1,需要进行的基本操作次数=40.
  • i=2,需要进行的基本操作次数=40.
  • i=3,需要进行的基本操作次数=40.
  • ……
  • i=n,需要进行的基本操作次数=40.
• 可能在n范围小的时候不算是优化，但是现在规模是10^4.这样优化以后时间复杂度就是O(40n)已经是一次线性了，很优化了。

方法二：

可以定义两个线性表（数组），一个记录d(n)操作的值，另一个记录是否生成过（0/1标记），此后查找就不需要for循环，直接看用于记录的数组的值是0/1，判断是否生成过。 //以下是标记法，简化成了一个数组完成

#include<stdio.h>
#define L(x) for(x=0;x<10;++x)
int main(){
int i,j,k,m,n,a[10036]={0}；//能生成最大的数为10035
L(i)L(j)L(k)L(m)
	a[1001*i+101*j+11*k+2*m]=1;//ijkm生成的数，标记为1
for(i=1;i<10000;++i)
	if(a[i]==0)//i没有被生成过
		printf("%d\n",i);
return 0;

}

3.递归类算法复杂度分析

①n！需要计算n次乘法。

int f(int n){
if n==0 return 1;
return f(n-1)*n
} 假如计算f(n-1)需要M(n-1)次乘法运算。那么M(n)=M(n-1)+1=M(n-2)+2=……=M(0)+n=n。

递归阶层运算的时间复杂度：n

②hanoi问题

复杂度：
if n=1 M(n)=1
if n>1 M(n)=M(n-1)+1+M(n-1)
	=2xM(n-1)+1
	=2²xM(n-2)+2+1
	=2^(n-1)+……+2+1=(2^n)-1

③斐波拉西序列

int fib（n）{
if n<2 return n;
return fib(n-1)+fib(n-2);
}

复杂度（也是斐波拉西序列的通项公式）:

基本操作：加法。记操作加法的次数为M

• if n=0,1 M(n)=0
• if n>1 M(n)=M(n-1)+M(n-2)+1（这里的1是fib(n-1)+fib(n-2)间的加法）
• Let B(n)=M(n)+1————(B(n)=M(n)+1=M(n-1)+1+M(n-2)+1)
• when n=0 or n=1,B(n)=1
• B(n)=B(n-1)+B(n-2)=2B(n-2)+B(n-3)=……=fib(n+1)(这个时间复杂度恰好是斐波拉西序列)
• M(n)=B(n)-1=1.618^n

优化：关于斐波那契数列三种解法及时间复杂度分析

两个以上的递归要十分小心，复杂度是以指数增长的。一般都会超时。

五、补充拓展

PS：现在的能力还不太看得懂米勒测试，蒙哥马利算法 所以先码着参考

• 蒙哥马利算法详解

• 素数判断算法 - 拉宾-米勒测试定理

再配上两张长图

• Previous
  “汉诺塔问题变式及解析”
• Next
  ”「致曾经的入门」ACM算法课二(经典数据结构与算法)“