洛谷训练（3）时间复杂度分析、欧拉筛法求素数、next_permuatation()、sort()_计算复杂度,洛谷

一、时间复杂度分析

在ACM比赛中，每道题都对时间和空间大小进行了限制。 有时不惜用空间换时间的方法来使题目AC。

1. 只关注循环执行次数最多的一段代码

int cal(int n)
{
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i)
   {
   	sum = sum + i;
   }
   return sum;
}
1
2
3
4
5
6
7
8
9
10

其中第2、 3行代码都是常量级的执行时间，与n的大小无关，所以对于复杂度并没有影响。循环执行次数最多的是第4、 5行代码，所以这块代码要重点分析。这两行代码被执行了n次，所以总的时间复杂度就是O(n)。

2. 加法原则：总复杂度等于量级最大的那段代码的复杂度

int cal(int n)
{
	int sum_1 = 0;
	int p = 1;
	for (; p < 100; ++p)
	{
		sum_1 = sum_1 + p;
	}
	int sum_2 = 0;
	int q = 1;
	for (; q < n; ++q)
	{
		sum_2 = sum_2 + q;
	}
	int sum_3 = 0;
	int i = 1;
	int j = 1;
	for (; i <= n; ++i)
	{
		j = 1;
		for (; j <= n; ++j)
		{
			sum_3 = sum_3 + i * j;
		}
	}
	return sum_1 + sum_2 + sum_3;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

综合这三段代码的时间复杂度，我们取其中最大的量级。所以，整段代码的时间复杂度就为O(n2)。也就是说： 总的时间复杂度就等于量级最大的那段代码的时间
复杂度。那我们将这个规律抽象成公式就是：
如果T1(n)=O(f(n))， T2(n)=O(g(n))；那么T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n))).

3. 乘法原则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

int cal(int n)
{
	int ret = 0;
	int i = 1;
	for (; i < n; ++i)
	{
		ret = ret + f(i);
	}
}
int f(int n)
{
	int sum = 0;
	int i = 1;
	for (; i < n; ++i)
	{
		sum = sum + i;
	}
	return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

我们单独看cal()函数。假设f()只是一个普通的操作，那第4～6行的时间复杂度就是， T1(n) = O(n)。但f()函数本身不是一个简单的操作，它的时间复杂度是T2(n) =O(n)，所以，整个cal()函数的时间复杂度就是， T(n) = T1(n) * T2(n) = O(n*n) = O(n2)。

二、欧拉筛法求素数

• 时间复杂度为O(n)

const int maxn=100000001;
int prime[maxn];      //就是个素数表
bool sf[maxn];        //判断这个数是不是素数，sf[i]中的i是从1到maxn的数
void sushu(){         //核心 欧拉筛代码
    int num=0;        //num 用来记筛到第几个质数
    memset(sf,true,sizeof(sf));
    for(int i=2;i<=maxn;i++){          //外层枚举1~maxn
        if(sf[i]) prime[++num]=i;      //如果是质数就加入素数表
        for(int j=1;j<=num;j++){       //内层枚举num以内的质数
            if(i*prime[j]>maxn) break; //筛完结束
            sf[i*prime[j]]=false;      //筛掉...
            if(i%prime[j]==0) break;   //避免重复筛
        }
    }
    sf[1]=false;
    sf[0]=false;  //1 0 特判 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

三、全排列函数next_permutation()

next_permutation()函数将按字母表顺序生成给定序列的下一个较大的排列，直到整个序列为降序为止。prev_permutation()函数与之相反，是生成给定序列的上一个较小的排列。

这是一个求一个排序的下一个排列的函数，可以遍历全排列,要包含头文件#include < algorithm >

使用方法：next_permutation(数组头地址，数组尾地址);若下一个排列存在，则返回真，如果不存在则返回假

若求上一个排列，则用prev_permutation

int a[];
do{
  
  }while(next_permutation(a,a+n));
1
2
3
4

• 洛谷新手村P1618三连击（升级版）可使用该函数进行全排列

#include <iostream>
#include <algorithm> 
using namespace std;

int main()
{
	int a,b,c,arr[9]={1,2,3,4,5,6,7,8,9};//先把每个数字放进数组 
	int flag=1;//设置标志，如果flag==1，说明不满足条件 
	int A,B,C;
	cin>>A>>B>>C;
	do{
		
		a=arr[0]*100+arr[1]*10+arr[2];
		b=arr[3]*100+arr[4]*10+arr[5];
		c=arr[6]*100+arr[7]*10+arr[8];
		if((A+B+C)*a==(a+b+c)*A&&(A+B+C)*b==(a+b+c)*B&&(A+B+C)*c==(a+b+c)*C)
		{
			flag=0;
			cout<<a<<" "<<b<<" "<<c<<endl;
		}	
		
	}while(next_permutation(arr,arr+9));
	if(flag)
		cout<<"No!!!";
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

四、排序函数sort()

• sort()函数对给定区间所有元素进行排序，默认为升序，也可进行降序排序。
• sort()类似于快速排序的方法，时间复杂度为O(nlogn)
• sort(start,end,cmp)
  （1）start表示要排序数组的起始地址；
  （2）end表示数组结束地址的下一位；
  （3）cmp用于规定排序的方法，可不填，默认升序。

洛谷新手村P1478陶陶摘苹果（升级版）中我用到了此函数对结构体数组进行排序

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int xi;
	int yi;
}arr[5010];

bool cmp(node re1,node re2)
{
	return re1.yi<re2.yi;//注意不能加“=”，否则数据量大了数组会溢出
}
int main()
{
	int cnt=0;
	int n,s;
	cin>>n>>s;
	int a,b;
	cin>>a>>b;
	int height=a+b;
	for(int i=0;i<n;i++) 
	{
		int x,y;
		cin>>x>>y;
		if(x<=height)
		{
			arr[i].xi=x;
			arr[i].yi=y;
		}
		else 
		{
			i--;
			n--;
		}	
	}
	sort(arr,arr+n,cmp);
	for(int i=0;i<n;i++)
	{
		if(s>0)
		{
			cnt++;
			s-=arr[i].yi;
			if(s<0)
			{
				cnt--;
				break;
			}
		}
	}
	cout<<cnt;
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

五、0-1背包问题

• 背包问题分为可拆分和不可拆分（即0-1背包）
• 个人在学背包问题时，似懂非懂，以下这篇博文讲的十分清晰
  0-1背包问题图文并茂