山东普及组分数线55

小学组43

首先：

  常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n^2)＜Ο(n^3)＜…＜Ο(2^n)＜Ο(n!)

时间复杂度可以简单理解为最多执行次数。

一、O(1)

一般情况下没有其他循环和递归调用，时间复杂度一般都是O(1)。比如下面这样的代码

#include<iostream>  using namespace std;  int main(){  	int a=0,b=0,x=0,y=0;  	cin>>a>>b;  	x=a+b;  	y=a-b;  	if(x>y){  	 cout<<x;  	}else{  	 cout<<y;  	}  	return 0;  }

二、O(n)

一般情况下，一个循环的时间复杂度是O(n)，多个循环并列也是取循环次数最多的那个作为时间复杂度。当数据量增大n倍，耗时增大n倍。

#include<iostream>  using namespace std;  int main(){  	int a=n;  	cin>>n;  	for(int i=0;i<n;i++){  	    cout<<i;  	}  	return 0;  }

三、O(n2)、O(n*m)

双重循环嵌套一般就是O(n2)。当数据量增大n倍，耗时增大n方倍。

#include<iostream>  using namespace std;  int main(){  	int n=0;  	cin>>n;  	for(int i=0;i<n;i++){  	    for(int j=0;j<n;j++){  	        cout<<i;  	    }  	}  	return 0;  }

如果循环嵌套外层循环是n，内层循环是m。

#include<iostream>  using namespace std;  int main(){  	int n=0,m=0;  	cin>>n>>m;  	for(int i=0;i<n;i++){  	    for(int j=0;j<m;j++){  	        cout<<i;  	    }  	}  	return 0;  }

这个时候的时间复杂度是O(n*m)。

四、O(logn)

当数据增大n倍时，耗时增大logn倍。

#include<iostream>  using namespace std;  int main(){  	int n=0;  	cin>>n;  	for(int i=0;i<n;i++){  	   i*=2;  	   cout<<i;  	}  	return 0;  }

本来循环次数是n，现在i*=2了。那么答案是log(2)(n)。

反着想也可以，原来循环n次，现在每次i变成原来的2倍，也就是2的k次方等于n。那么正好就是log(2)(n)，即O(log n)

或者下面这样：

#include<iostream>using namespace std;  int main(){  int n=0;  cin>>n;  while((n=n/2)>0){      cout<<n;  }   return 0;  }

时间复杂度也是O(logn)

五、O(nlogn)

一般归并排序和堆排序是O(nlogn)。 

常见的是外层循环的时间复杂度是n，内层循环的时间复杂度是logn。

比如下面这样：

for(int i=1; i<=n; i++)  {  	for(int j=1; j<=n; j+=i)  	{  		.....   //复杂度为O(1);  	}  }

注意：外层循环是n，内层循环j每次都增加i。

1.方程求解

【描述】

输入正整数 a，b，c。

求有多少组 x 和 y 满足 a*x+b*y=c 。x 和 y 都是非负整数。

【输入】

一行，包含三个正整数 a，b，c，两个整数之间用单个空格隔开。

【输出】

满足 a*x+b*y=c 的 x 和 y 的组数。

【输入样例】

2 3 18

【输出样例】

4

【样例说明】

有以下 4 组 x 和 y 满足 2*x+3*y=18:

x=0,y= 6

x=3,y= 4

x=6 ,y=2

x=9,y= 0

【数据范围】

50%的数据，1<=a,b,c<=1000；

100%的数据，1<=a,b,c<=100000。