Time complexity and space complexity

p.s. It's the annual school season again ~

Time complexity

When the amount of data becomes larger , The program runs longer , We use complexity to describe the relationship between program running time and data volume
Program 1：

int cnt,a[100005];
for(int i=1;i<=n;i++)cnt+=a[i];

This program puts $a[1]$ To $a[n]$ Add up , So the running time of the program is the same as $n$ It's linear , Remember to do $O(n)$

Program 2：

int cnt,a[100005][100005];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)cnt+=a[i][j];

This program puts $a[1][1]$ To $a[n][n]$ Add up , So the running time of the program is the same as $n^2$ It's linear , Write it down as $O(n^2)$

Some common time complexity

Bubble sort 、 Selection sort $O(n^2)$
Merge sort 、 Quick sort $O(nlogn)$
Ethmoidal method $O(nlogn)$
Euler sieve method $O(n)$

The significance of computational complexity

The evaluation machine runs in about one second $5\ast 10^8$ Time , That is, the evaluation machine can run in one second $5\ast 10^8$ A simple operation $(+/-\ast )$ You need to control the complexity within $5\ast 10^8$ Within times of simple operation .

So we can also choose the algorithm by observing the data range , If it is $10^4$ The complexity can be used as $O(n^2)$ The algorithm of ,$10^6$ Sure $O(nlogn)$ too ,$10^8$ Sure $O(n)$ too , exceed $10^8$ Just $O(1)$ too , That is, find out the law and judge directly .

Differential array and prefix array

example 1：
There is an array with length n Array of $a[i]$,$q$ Group inquiry , Every time I ask $1$ To $m$ in ,$a[1]+a[2]+a[3]+...a[m]$ And
$n=10^6,q=10^6,1<=m<=n$

Idea one ： Every time I go $a[1]$ To $a[m]$ Add up

for(int i=1;i<=m;i++)sum+=a[i];
printf("%d\n",sum);

Complexity is $O(nq)$（ Because at most $n$ All the numbers add up , At most $q$ Time ）, once $n,q$ Is greater than $10^5$, Our program timed out .
Because before $i$ The number and , And the former $i+1$ The sum of the numbers only differs $a[i+1]$, There is no need to add it again every time , Therefore, the following methods are used to optimize it .

int a[100000],presum[100005];
for(int i=1;i<=n;i++)presum[i]=presum[i-1]+a[i];/// Add it first 
printf("%d",presum[m]);

In this way, the complexity of each inquiry becomes $O(n)$（ Just started to get $presum$ The array needs $O(n)$ Time for ）, In theory, it can be done through $10^8$ The data of the , But when we submitted the program, we found that it was still $TLE$ 了 , The reason is that synchronization flow is not related …

Just handled $presum$ Arrays are prefixes and arrays , In this way, we can reduce the complexity of finding the sum of intervals very low , To calculate ${\sum }_{i=l}^{r}a[i]$ Just output $presum[r]-presum[l-1]$ That's all right. , Save time .

example 2：
For a length of $n(n<10^6)$ Sequence , We're going to do $m$ operations . Every time I give it to you $l,r$, Let you $a[l],a[l+1]...,a[r]$ All plus one , Output $m$ The sequence after the first operation .

If we put $a[i]$ To $a[j]$ all 1, Complexity is $O(nq)$.
If title $m=10^6$, Every time $l=1,r=10^6$, It's over time .
At this time, we need to use an approximate optimization method ： Difference array To optimize
Let's start with an array $b[N]$
When the operation makes $a[l],a[l+1]...,a[r]$ All add one hour , We make $b[l]++$,$b[r+1]--$
At this point we observe b[N] Array and its prefix and ：
b Array
$00000001_{The\; firstlposition}00000(-1{)}_{The\; firstr+1position}000$
b Prefix and array preb
$00000001_{The\; firstlposition}1111110_{The\; firstr+1position}00$
Find out $b$ Prefix and array $preb$ Is what we want $a$ Array
This technique of using auxiliary arrays to optimize interval addition and subtraction is called differential array

That is to record $a[i]-a[i-1]$ Value , The complexity of interval modification becomes $O(1)$（ Only need to modify $a[i]$ and $a[j+1]$）, Just the complexity of querying a single element becomes $O(n)$, Because you have to add up all the elements before it .

Reduce the number of repeated operations and reduce the time complexity ：

Preprocessing

The prefix and mentioned above are the most common preprocessing methods . Preprocessing is a technique to improve program efficiency by processing some frequently used data in calculation in advance . The complexity of query results is $O(1)$, Therefore, in the face of multiple groups of queries, we only need to pay the time complexity of preprocessing .
Here are some algorithms of prime numbers as examples ：
In general , The complexity of judging whether a number is a prime number is $O(n^{1/2})$. Judge $m$ The complexity of primes can be optimized to a very low , Because the prime numbers in a certain range are screened out before judgment , This can also be seen as a preprocessing optimization .

Some dry goods ：《 Harmonic series optimization complexity 》

When learning the prime sieve method, we learned a kind of garbage sieve called the Egyptian sieve , His method is to enumerate the number and then enumerate the multiples of this number . The overall complexity is based on harmonic series $O(nlogn)$

I recall that I did this optimized topic at the beginning of school Example ： Maximum gcd, It is also calculated in the same way $gcd$ It becomes enumeration $gcd$ Multiple
Another use Harmonic series Optimize the complexity of the problem CF484B
In fact, in retrospect, the ideas are very similar ,$gcd$ Or the remainder can be enumerated $a[i]$ To calculate the multiple of

Spatial complexity

Each program has an allowable memory size , If you exceed the allowed memory, you will receive $MLE$ A hint of .
So how to calculate the allowed memory ？
We know one $int$ Array needs to spend $32$ Two binary bits to store , And a byte contains $8$ Binary bits
So easy to calculate ,$512MB$ Memory can be stored $512\ast 1024\ast 1024\ast 8/32\approx 5\ast 10^7$ individual $int$, So it's commonly used $512MB->6\ast 10^7$ You can know by proportional conversion $a[N]$ Medium $N$ How big can I drive ~

Scrolling array

When $dp[i][j]$ The transfer of is only related to $dp[i-1][...]$ When it comes to space, we can change it from $n^2$ Compression - $2\ast n$~