• 时间复杂度和空间复杂度


    🏠个人主页:泡泡牛奶

    🌵系列专栏:[C语言] 数据结构奋斗100天

    本章将会带你走入C语言数据结构与算法的大门,让你领会新的世界( •̀ ω •́ )✧

    说到数据结构与算法,就不得不提到算法效率的好坏了,本章将会让你了解什么叫时间复杂度,什么叫空间复杂度,速速让我们开始吧<( ̄︶ ̄)↗[GO!]

    1. 算法的效率

    有些人认为,代码越简洁,代码就越好,那么是不是这样呢?请随我接下来看。

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

    请看下面求斐波那契数列:

    long Fib(int N)
    {
    	if(N < 3)
    		return 1;
        else
    		return Fib(N-1) + Fib(N-2);
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    可以看到代码非常的简洁,那是否代码效率是否就很高呢?

    时间复杂度-1

    时间却用了几分钟才能把结果算出来,可以想到,数字才到50就用了几分钟才能将结果算出来,可见代码简洁有时候不一定效率就高。

    那么,算法的效率该如何评断呢?

    1.2 算法的复杂度

    衡量一个代码的好坏,往往需要通过所消耗的时间资源空间资源来判断。我们经常用复杂度来衡量代码的效率。

    时间复杂度主要衡量一个算法运行大概需要的时间,空间复杂度主要衡量一个算法运行时所需要的额外空间

    这里可能会有些疑问,说这么多复杂度到底是什么🤔?

    复杂度:就是一个数学函数表达式,通常用 大写字母O (Operation)来表示

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

    2. 时间复杂度

    2.1 时间复杂度概念

    我们要知道,一个算法所执行所消耗的时间,从理论上来说,是不可能计算出来的,只有你把程序放在机器上跑起来才能知道所消耗的时间,而每一台机器根据硬件的不同,所消耗的时间又会有所差异,那么,时间复杂度到底怎样表示呢?

    时间复杂度:

    时间复杂度就是算法所要执行基本操作的执行次数

    即:找到某条与基本语句与问题规模N之间的数学表达式,就是该算法的时间复杂度

    请看下面一串代码:

    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);
    }
    
    • 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

    fun 执行的基本操作次数为:
    F ( N ) = N 2 + 2 N + 10 F(N) = N^2 + 2N + 10 F(N)=N2+2N+10
    在实际计算空间复杂度时,我们其实并不一定需要计算精确的执行次数,而只需要大致执行次数,那么这就是我们所使用的大O的渐进表示法

    2.2 大O的渐进表示法

    大O符号(Big O),用于描述函数渐进行为的数学符号。

    大O渐进表示法:

    • O(1) 来表示所有常数
    • 只保留最高次幂项
    • 将最高项数的系数去除
    • 计算时,计算最坏的情况

    所以上面 fun 用大O的渐进表示法表示就是 O ( N 2 ) O(N^2) O(N2)

    注意:

    千万不能通过看循环层数来直接判断时间复杂度,一定要通过分析算法的方式来计算

    3. 空间复杂度

    空间复杂度:

    空间复杂度就是一个算法所需要额外开辟的空间。

    但相比于时间,开辟过的空间可以重复利用

    举个栗子🌰:

    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;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    在这个函数中我们第一次动态开辟了一段 N+1 大小的一段空间,释放掉空间之后,又开辟了一段 N+1 大小的一段空间,那么这一段的空间复杂度是多少呢?

    答案:O(n)

    解释:

    1. 空间复杂度,同样采用大O渐进表示法
    2. 开辟过的空间释放掉之后,之后想再次用,会在原来的地方重新申请一块空间(这段空间与原来空间大小相同)

    4. 常见复杂度对比

    一般常见的复杂度如下:

    数学函数例子大O渐进表示法阶级
    114514O(1)常数阶
    3logn + 4O(logn)对数阶
    2n+4O(n)线性阶
    2n+3nlogn+14O(nlogn)nlogn阶
    3n^2 + 2n +4O(n^2)平方阶
    n^3 + n^2 +n +1O(n^3)立方阶
    2^nO(2^n)指数阶
    n!O(n!)阶乘阶

    阶级从上往下依次增大,越往下复杂度越高,效率越低


    现在我们想必已近对时间复杂度和空间复杂度有一定的理解了吧,那么,从新返回到开头,试着用我们刚认识的新知识来判断一下 递归算法求斐波那契数的时间复杂度空间复杂度吧😀。

    long Fib(int N)
    {
    	if(N < 3)
    		return 1;
        else
    		return Fib(N-1) + Fib(N-2);
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    时间复杂度:

    答案:O(2^n)

    解析:

    image-20220805174512855

    通过画图分析,我们可以推测到当 N>=3 时,递归从N开始,每调用一次递归,都需要执行两次,综合以上推断,执行的次数就是2^n ,故答案为2^n

    空间复杂度:

    答案:O(n)

    解析:

    时间复杂度-2

    首先我们要注意一点,内存是可以重复利用的,假设一直递归递归到最底层之后,是先结束最后一层的函数调用所开辟的栈帧,然后才为另外一侧的栈帧开辟空间,这样我们根据这个道理,列出数学函数表达式(具体的复杂度)O(n-3) ,则空间复杂度为O(n)


    好啦(/≧▽≦)/, 本期的内容就到这里,如果对你有帮助的话,还不忘给一个大大的三连😘,这对我真的很重要ο(=•ω<=)ρ⌒☆

  • 相关阅读:
    LVGL学习(5):物理按键切换焦点之焦点保存和恢复
    插入排序(Insertion Sort)
    Change Buffer 只适用于非唯一索引页?错
    【榜单公布】10·24征文活动结果出炉!
    C++用锁实现线程安全的stack容器
    信息学奥赛一本通:2042:【例5.10】稀疏矩阵
    prometheus helm install 如何配置告警模版
    【Flask介绍】
    js的this及this的指向是什么
    一直以来,人们都在试图寻找产业互联网真实的样子
  • 原文地址:https://blog.csdn.net/xiao_feng0211/article/details/126183777