个人主页：泡泡牛奶

系列专栏：[C语言] data structure struggle100天

This chapter will take you throughCThe Gateway to Language Data Structures and Algorithms,Let you understand the new world( •̀ ω •́ )*

Speaking of Data Structures and Algorithms,I have to mention the efficiency of the algorithm.,This chapter will give you an idea of ​​what time complexity is,what is space complexity,Quick let's get started<(￣︶￣)[GO!]

1. 算法的效率

有些人认为,代码越简洁,代码就越好,那么是不是这样呢？please follow me.

1.1 如何衡量一个算法的好坏？

See below for the Fibonacci sequence：

long Fib(int N)
{
    
	if(N < 3)
		return 1;
    else
		return Fib(N-1) + Fib(N-2);
}

You can see that the code is very concise,Is the code efficient?？

It took a few minutes to calculate the result,可以想到,numbers are coming50It only took a few minutes to calculate the result,It can be seen that the code is concise and sometimes not necessarily efficient.

那么,How to judge the efficiency of an algorithm?？

1.2 算法的复杂度

measure the quality of a code,It is often necessary to pass the consumed时间资源和空间资源来判断.我们经常用复杂度to measure the efficiency of the code.

Main measure an algorithm running time complexity大概所需要的时间,Space complexity mainly measures the amount of time an algorithm needs to run额外空间

这里可能会有些疑问,说这么多what is complexity？

复杂度：就是一个数学函数表达式,通常用 大写字母O_{（Operation）}来表示

例如：O(n^2 + 2n + 1)

2. 时间复杂度

2.1 时间复杂度概念

我们要知道,The time it takes for an algorithm to execute,从理论上来说,it is impossible to calculate,Only when you put the program on the machine and run it can you know the time it takes,And each machine is different according to the hardware,The time consumed will vary,那么,How is the time complexity expressed?？

时间复杂度：

Is time complexity of the algorithm to perform basic operation执行次数.

即：Find a certain sentence with basic statement and problem sizeN之间的数学表达式,is the time complexity of the algorithm

请看下面一串代码：

void fun(int N)
{
    
    int count = 0;
    
    //1
    for (int i = 0; i < N; ++i)
    {
    
        for (int j = 0; j < N; ++j)
        {
    
            ++count;
        }
    }
    
    //2
    for (int i = 0; i < 2*N; ++i)
    {
    
        ++count;
    }
    
    //3
    int M = 10;
    while (M--)
    {
    
        ++count;
    }
    
    printf("%d\n", count);
}

fun 执行的基本操作次数为：
$$F(N)=N^2+2N+10$$
When actually calculating the space complexity,We don't actually need to count the exact number of executions,而只需要Approximate execution times,then this is what we use大O的渐进表示法.

2.2 大O的渐进表示法

大O符号（Big O）,用于描述函数渐进行为的数学符号.

大O渐进表示法：

• 用 O(1) 来表示所有常数
• 只保留最高次幂项
• remove the coefficient of the highest number of terms
• 计算时,计算最坏的情况

所以上面 fun 用大OThe progressive notation representation of is $$O(N^2)$$

注意：

Never directly judge the time complexity by looking at the number of loop layers,It must be calculated by means of an analytical algorithm

3. 空间复杂度

空间复杂度：

Space complexity is what an algorithm needs额外开辟的空间.

but compared to time,open space是可以重复利用的

举个栗子：

void fun(int *nums, int N)
{
    
    int* arr1 = (int*)calloc(N+1, sizeof(int));
    //....操作
    free(arr1);
    arr1 = NULL;
    
    int* arr2 = (int*)calloc(N+1, sizeof(int));
    //....操作
    free(arr2);
    arr2 = NULL;
}

In this function we dynamically open a section for the first time N+1 size of space,After freeing up space,opened up again N+1 size of space,Then this paragraph空间复杂度是多少呢？

答案：O(n)

解释：

1. 空间复杂度,also use largeO渐进表示法
2. After the opened space is released,want to use it again,Will re-apply for a space in the original place_{（This space is the same size as the original space）}

4. 常见复杂度对比

The common complexity is as follows：

Classes increase from top to bottom,The further down, the higher the complexity,效率越低

Now we must have a certain understanding of time complexity and space complexity.,那么,back to the beginning,Try to judge with the new knowledge we just met 递归算法Find Fibonacci numbers时间复杂度和空间复杂度吧.

long Fib(int N)
{
    
	if(N < 3)
		return 1;
    else
		return Fib(N-1) + Fib(N-2);
}

时间复杂度：

答案：O(2^n)

解析：

Analysis by drawing,We can speculate that when N>=3 时,递归从N开始,Recursion per call,need to be executed twice,Based on the above inferences,执行的次数就是2^n ,故答案为2^n

空间复杂度：

答案：O(n)

解析：

First we have to pay attention to,memory is reusable,Assuming recursive recursion to the bottom,是先结束最后一层的函数调用Open up the stack frame,and then for the other side的栈帧开辟空间,Therefore, according to this,List mathematical function expressions_{(specific complexity)}O(n-3) ,则空间复杂度为O(n)

好啦(/≧▽≦)/, 本期的内容就到这里,如果对你有帮助的话,Don't forget to give a big three,这对我真的很重要ο(=•ω＜=)ρ⌒*