Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Preface

To know what null/time complexity is, you need to know what data structures are.

This can be understood in two ways. Data exists everywhere in our lives, such as the international events on Douyin, the Emperor Yongzheng taking off his armor, and so on. All the data that we users can see are the data stored on Douyin's backend servers. However, these data have one feature, that is, they are all on Douyin's hot search list, and this list is the structure, which ensures that the data is in a fixed location for users to browse.

In addition, with data structure, algorithms are indispensable. As we just said, data structure is to store data in a structure in a regular manner, so how to efficiently access data from the structure is the algorithm.

time complexity

With algorithms, there are time complexity and space complexity. As computers now have larger and larger memory, time complexity is more important than space complexity. So let's first understand time complexity.

concept

The most important word in time complexity is time. Here, time refers to the time it takes a program to run. If the time complexity is smaller, then the algorithm is better. Time complexity calculation is expressed by the function T(N)

So why don't we calculate the time complexity of this program in advance and write the optimal solution code? This involves the problem of computers.

1. Because the program running time is related to the compilation environment and the configuration of the running machine, for example, an algorithm program can be compiled with an old
   Compiling with the old compiler and compiling with the new compiler will take different amounts of time on the same machine.
2. The same algorithm program will take different amounts of time to run on an old low-configuration machine and a new high-configuration machine.
3. Furthermore, time can only be tested after the program is written and cannot be calculated and evaluated through theoretical ideas before writing the program.

Let's look at a piece of code:

// 请计算⼀下Func1中count语句总共执⾏了多少
次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;
}
}
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

This code should look like this based on the number of times count is executed:
T (N) = N2 + 2 ∗ N + 10
• N = 10 T(N) = 130
• N = 100 T(N) = 10210
• N = 1000 T(N) = 1002010

At this time, someone said, doesn't int count = 0 count?

Here we underestimate our computer. Our computer CPU can execute hundreds of millions of times per second. This small time can of course be ignored. So the time complexity we calculated is not accurate, but just a rough estimate. At this time, we use a new symbol to represent it.

Asymptotic representation of Big O

Big O notation: A mathematical notation used to describe the asymptotic behavior of a function; it is used here to represent the estimated time complexity.

So is it still the same as T(N)? If so, we don't need to use another symbol. Here comes the rule of calculating O:

1. In the time complexity function T(N), only the highest-order terms are retained and the lower-order terms are removed. This is because as N continues to grow, the lower-order terms have less and less impact on the results. When N is infinite, they can be ignored.
2. If the highest-order term exists and is not 1, remove the constant coefficient of this term, because as N continues to increase, this coefficient has less and less impact on the result, and when N is infinite, it can be ignored.
3. If there are no items related to N in T(N), only constant items, replace all additive constants with the constant 1.

Then let's look at T(N)=N^2+2∗N+10 above. The highest order here is N2, so if we remove the other low-order ones, the complexity is (ON^2).

Small scale chopper

// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++ k)
{
++count;
}
for (int k = 0; k < N ; ++
k)
{
++count;
}
printf("%dn", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Here T(N)=M+N, then let's calculate O(N). Here M and N are of the same order, so it does not meet the first rule, nor does it correspond to the second and third rules, so it is o(N+M). Then someone asked, what if N is larger than M, shouldn't it be O(N). Here the question is, how do you know that N is larger than M? What if M is larger than N? So for the sake of insurance, we all stay.

// 计算strchr的时间复杂度？
const char * strchr ( const char
 * str, int character)
{
const char* p_begin = s;
while (*p_begin != character)
{
if (*p_begin == '0')
return NULL;
p_begin++;
}
return p_begin;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

Here we are looking for the position of character in str. Here I add a knowledge point:

• Our O calculation is generally the worst-case complexity of an algorithm.
  This can be divided into three levels of complexity:
  1. Best case scenario
  To find the character at the first position in a string, then:
  F (N) = 1, complexity is o(1)

2. Average situation:
To find the character in the middle of a string:
F (N) = N/2,O(N/2)

3. Worst case scenario
To find the character at the end of the string:
F (N) = N,O(N)

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

In the worst case, because we keep the higher order and remove n/2 (the first one) and ignore the coefficient (the second one), we get ON^2

void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
1
2
3
4
5
6
7
8

When n=2, the execution count is 1
When n=4, the execution times is 2
When n=16, the number of executions is 4
Assume the number of executions is x, then 2
x = n
Therefore, the number of executions is: x = log n
Therefore, the worst case time complexity of func5 is:
O(log2 ^n)

Different books have different ways of expressing it. The above expressions are not much different. We recommend using log n

Space complexity

It should be noted that the space complexity is also expressed in O, and its rules follow the same three rules as the time complexity.

Notice

The stack space required for function execution (to store parameters, local variables, some register information, etc.) is determined during compilation, so the space complexity is mainly determined by the additional space explicitly requested by the function when it is running.

example 1:

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

The function stack frame is determined during compilation.
You only need to pay attention to the additional space allocated when the function is running.
BubbleSort additional space required
A finite number of local variables such as exchange use a constant amount of extra space
Therefore, the space complexity is O(1)