山东普及组分数线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。

【题目描述】

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

【输入描述】

输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。

n=0表示输入数据的结束，不做处理。

【输出描述】

对于每个测试实例，输出在第n年的时候母牛的数量。

每个输出占一行

【样例输入】

2  4  5  0

【样例输出】

2  4  6