# [ACM training I] time complexity, recursion and enumeration

## Time complexity

Common time complexity (Big O representation)
(1) O(1): constant order, running time is constant
(2) O(logn): logarithmic order, such as binary search algorithm
(3) O(n): linear order, such as finding the maximum value within n numbers
(4) O(nlogn): logarithmic order, such as fast sorting algorithm
(5) O(n^2): square order, if sorting is selected, bubble sorting
(6) O(n^3): cubic order, such as multiplication of two n-order matrices
(7) O(2^n): algorithm of exponential order, such as all subsets of N element sets
(8) O(n!): factorial order, such as the algorithm for arranging all n elements

## Enumeration and recursion

No explanation for the definition
Example
1. Enumeration improvement
Input a number n (0 < n < 8) and a number k (0 < K < = 5). Requirements: select any k numbers from the N numbers of 1~N (numbers can be selected repeatedly). Please output all schemes according to the size.

```#include <stdio.h>
int n,k;
int tt[9];
void di(int pt)
{
int i;
if(pt>k)
{
for(i=1;i<=k;i++)
printf("%d",tt[i]);
printf("\n");
}
else
{
for(i=1;i<=n;i++)
{
tt[pt]=i;
di(pt+1);
}
}
}
int main()
{
scanf("%d%d",&n,&k);
di(1);
return 0;
}
```

2. Full arrangement
Input a number n (0 < n < 8), and output a total arrangement of N numbers from 1 to N in order of small to large.

```#include<stdio.h>
#include<math.h>
int main(){
int used[10];
int N,i,j,k,s,t;
int min=0,max=0;
scanf("%d",&N);
for(i=1;i<=N;i++)
{
min=min+i*pow(10,N-i);
max=max+(N-i+1)*pow(10,N-i);
}
for(i=min;i<=max;i++)
{
used[1]=0;
used[2]=0;
used[3]=0;
used[4]=0;
used[5]=0;
used[6]=0;
used[7]=0;
used[8]=0;
for(j=1,k=i;j<=N;j++)
{
s=k/pow(10,N-j);
k=k-(s*pow(10,N-j));
switch(s)
{
case 0:used[0]=used[0]+1;break;
case 1:used[1]=used[1]+1;break;
case 2:used[2]=used[2]+1;break;
case 3:used[3]=used[3]+1;break;
case 4:used[4]=used[4]+1;break;
case 5:used[5]=used[5]+1;break;
case 6:used[6]=used[6]+1;break;
case 7:used[7]=used[7]+1;break;
case 8:used[8]=used[8]+1;break;
case 9:used[9]=used[9]+1;break;
}
}
for(j=1,k=0;j<=N;j++)
{
if(used[j]!=1)
break;
else
k=k+1;
}
if(k==N)
printf("%d\n",i);
}
}
```

3, Queen N
N queens are placed on the checkerboard of N*N, so that they do not attack each other (that is, any two queens are not allowed to be in the same row, the same column, or on the diagonal line with a 45 angle to the board frame).
Your task is to find out how many legal placement methods are available for a given N.

```#include <stdio.h>
#define NUMS 10
int N;
int chessboard[11][11];
int cal;
int dfs_check(int row,int column,int k)
{
if(row>k)
{
cal++;
return 1;
}
int i=0;
int j=0;
for( i = 1; i < row; i++)

if(chessboard[i][column] == 1)
return 0;

/* Check whether the upper left and right 45 degree angle is OK*/
/* Upper left*/
for( i=row-1,j=column-1;i>0&&j>0;i--,j--)
if(chessboard[i][j] == 1)
return 0;
/* Upper right*/
for( i=row-1,j=column+1;i>0&&j<=k;i--,j++)
if(chessboard[i][j] == 1)
return 0;
/*Mark this position successfully*/
chessboard[row][column] = 1;

/*Next line search*/
for( i=1;i<=k;i++)
if(dfs_check(row+1,i,k)==1)
break;

chessboard[row][column] = 0;
return 0;
}
int main()
{
int i,j,k;
int count[11];
/*charge by the meter*/
for(k=1;k<=NUMS;k++)
{
count[k] = 0;
cal = 0;
/*First, set all chessboard initialization to 0*/
for(i=0;i<=NUMS;i++)
for(j=0;j<=NUMS;j++)
chessboard[i][j]=0;
for(i=1;i<=k;i++)
dfs_check(1,i,k);
count[k] = cal;
}

while(scanf("%d",&N)!=EOF&&N!=0)
printf("%d\n",count[N]);
return 0;
}
```

To be continued

Posted on Sun, 03 Nov 2019 01:57:16 -0700 by jimdelong