山东普及组分数线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.指针与数组的关系

    指向数组的指针变量称为数组指针变量。“数组是内存上一块连续的空间”。数组名就是这块连续空间的首地址。

2.指针指向数组

    一开始的数组定义与输出：

#include<iostream>  #include<cstdio>  using namespace std;  int main(){  	int a[10];  	for(int i=0;i<5;i++){  		cin>>a[i];  	}  	for(int i=0;i<5;i++){  		cout<<a[i]<<" ";  	}  	return 0;  }

指针操作也可以输入数据：

#include<iostream>  #include<cstdio>  using namespace std;  int main(){  	int a[10];  	for(int i=0;i<5;i++){  		scanf("%d",a+i); //本来写成scanf("%d",&a[i]);   	}  	for(int i=0;i<5;i++){  		printf("%d ", *(a+i));  //  	}  	return 0;  }

上面这个操作，本来scanf("%d",&a)写法，其中&是取地址符，a是数组名，本来就表示数组空间的首地址，所以可以直接用。注意，这个地方不能用cin。

数组指向指针操作：

我们可以定义指针变量，让它来指向数组名。

#include<iostream>  #include<cstdio>  using namespace std;  int main(){  	int a[10];  	int *p=a;    	for(int i=0;i<5;i++){  		scanf("%d",p+i); //本来写成scanf("%d",&a[i]);   	}  	for(int i=0;i<5;i++){  		printf("%d ", *(p+i));   	}  	return 0;  }

2.指针的加减

指针也是变量，可以加减。

#include<iostream>  #include<cstdio>  using namespace std;  int main(){  	int a[10]={1,2,3,4,5};  	int *pa=a;    	cout<<a[0]<<endl; //结果是1   	cout<<pa<<endl;   //0x70fdf0  	cout<<*pa<<endl;  //结果是1  	  	pa++;  	cout<<pa<<endl; //0x70fdf4  	cout<<*pa<<endl;  //2  	  	pa=pa+2;  	cout<<pa<<endl; //0x70fdfc  	cout<<*pa<<endl;  //4  	  	pa--;  	cout<<pa<<endl; //0x70fdf8  	cout<<*pa<<endl;  //3   	return 0;  }