精华内容
下载资源
问答
  • 一套图 搞懂“时间复杂度

    万次阅读 多人点赞 2019-06-04 13:12:15
    是我到目前为止所看到的关于时间复杂度介绍的最好的文章,简介 清晰 明了。 所以拿来po出来 仅供学习交流,如侵则删。 现已将此文收录至:《数据结构》C语言版 (清华严蔚敏考研版) 全书知识梳理 正文: ...

    写在前面:

    这篇文章是在公众号: 程序员小灰 中发布的。是我到目前为止所看到的关于时间复杂度介绍的最好的文章,清晰明了。

    所以拿来po出来 仅供学习交流,如侵则删。

    现已将此文收录至: 《数据结构》C语言版 (清华严蔚敏考研版) 全书知识梳理

    同类好文: 8种方法优雅地利用C++编程从1乘到20

                       从B站 (哔哩哔哩) 泄露的源码里发现了B站视频推荐的秘密

                       Facebook前身 哈佛“选美”网站 核心算法 --- ELO等级分制度(附源码)


    正文: 

    640?wx_fmt=jpeg

    640?wx_fmt=jpeg

    640?wx_fmt=jpeg

    640?wx_fmt=jpeg

    640?wx_fmt=jpeg

    640?wx_fmt=jpeg

     

    640?wx_fmt=png

    时间复杂度的意义

     

    究竟什么是时间复杂度呢?让我们来想象一个场景:某一天,小灰和大黄同时加入了一个公司......

    640?wx_fmt=jpeg

    一天过后,小灰和大黄各自交付了代码,两端代码实现的功能都差不多。大黄的代码运行一次要花100毫秒,内存占用5MB。小灰的代码运行一次要花100秒,内存占用500MB。于是......

    640?wx_fmt=jpeg

    640?wx_fmt=jpeg

    由此可见,衡量代码的好坏,包括两个非常重要的指标:

    1.运行时间;

    2.占用空间。

    640?wx_fmt=jpeg

    640?wx_fmt=jpeg

     

    640?wx_fmt=png

    基本操作执行次数

     

    关于代码的基本操作执行次数,我们用四个生活中的场景,来做一下比喻:

    场景1:给小灰一条长10寸的面包,小灰每3天吃掉1寸,那么吃掉整个面包需要几天?

    640?wx_fmt=jpeg

    答案自然是 3 X 10 = 30天。

    如果面包的长度是 N 寸呢?

    此时吃掉整个面包,需要 3 X n = 3n 天。

    如果用一个函数来表达这个相对时间,可以记作 T(n) = 3n。

    场景2:给小灰一条长16寸的面包,小灰每5天吃掉面包剩余长度的一半,第一次吃掉8寸,第二次吃掉4寸,第三次吃掉2寸......那么小灰把面包吃得只剩下1寸,需要多少天呢?

    这个问题翻译一下,就是数字16不断地除以2,除几次以后的结果等于1?这里要涉及到数学当中的对数,以2位底,16的对数,可以简写为log16。

    因此,把面包吃得只剩下1寸,需要 5 X log16 = 5 X 4 = 20 天。

    如果面包的长度是 N 寸呢?

    需要 5 X logn = 5logn天,记作 T(n) = 5logn。

    场景3:给小灰一条长10寸的面包和一个鸡腿,小灰每2天吃掉一个鸡腿。那么小灰吃掉整个鸡腿需要多少天呢?

    640?wx_fmt=jpeg

    答案自然是2天。因为只说是吃掉鸡腿,和10寸的面包没有关系 。

    如果面包的长度是 N 寸呢?

    无论面包有多长,吃掉鸡腿的时间仍然是2天,记作 T(n) = 2。

    场景4:给小灰一条长10寸的面包,小灰吃掉第一个一寸需要1天时间,吃掉第二个一寸需要2天时间,吃掉第三个一寸需要3天时间.....每多吃一寸,所花的时间也多一天。那么小灰吃掉整个面包需要多少天呢?

    答案是从1累加到10的总和,也就是55天。

    如果面包的长度是 N 寸呢?

    此时吃掉整个面包,需要 1+2+3+......+ n-1 + n = (1+n)*n/2 = 0.5n^2 + 0.5n。

    记作 T(n) = 0.5n^2 + 0.5n。

    640?wx_fmt=jpeg

    上面所讲的是吃东西所花费的相对时间,这一思想同样适用于对程序基本操作执行次数的统计。刚才的四个场景,分别对应了程序中最常见的四种执行方式:

    场景1:T(n) = 3n,执行次数是线性的。

    void eat1(int n){
        for(int i=0; i<n; i++){;
            System.out.println("等待一天");
            System.out.println("等待一天");
            System.out.println("吃一寸面包");
        }
    }
    vo
    

    场景2:T(n) = 5logn,执行次数是对数的。

    void eat2(int n){
       for(int i=1; i<n; i*=2){
           System.out.println("等待一天");
           System.out.println("等待一天");
           System.out.println("等待一天");
           System.out.println("等待一天");
           System.out.println("吃一半面包");
       }
    }
    

    场景3:T(n) = 2,执行次数是常量的。

    void eat3(int n){
       System.out.println("等待一天");
       System.out.println("吃一个鸡腿");
    }
    

    场景4:T(n) = 0.5n^2 + 0.5n,执行次数是一个多项式。

    void eat4(int n){
       for(int i=0; i<n; i++){
           for(int j=0; j<i; j++){
               System.out.println("等待一天");
           }
           System.out.println("吃一寸面包");
       }
    }
    

     

    640?wx_fmt=png

    渐进时间复杂度

     

    有了基本操作执行次数的函数 T(n),是否就可以分析和比较一段代码的运行时间了呢?还是有一定的困难。

    比如算法A的相对时间是T(n)= 100n,算法B的相对时间是T(n)= 5n^2,这两个到底谁的运行时间更长一些?这就要看n的取值了。

    所以,这时候有了渐进时间复杂度(asymptotic time complexity)的概念,官方的定义如下:

    若存在函数 f(n),使得当n趋近于无穷大时,T(n)/ f(n)的极限值为不等于零的常数,则称 f(n)是T(n)的同数量级函数。

    记作 T(n)= O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

    渐进时间复杂度用大写O来表示,所以也被称为大O表示法。

    640?wx_fmt=jpeg

    640?wx_fmt=jpeg

    如何推导出时间复杂度呢?有如下几个原则:

    1. 如果运行时间是常数量级,用常数1表示;

    2. 只保留时间函数中的最高阶项;

    3. 如果最高阶项存在,则省去最高阶项前面的系数。

    让我们回头看看刚才的四个场景。

    场景1:

    T(n) = 3n 

    最高阶项为3n,省去系数3,转化的时间复杂度为:

    T(n) =  O(n)

    640?wx_fmt=png

    场景2:

    T(n) = 5logn 

    最高阶项为5logn,省去系数5,转化的时间复杂度为:

    T(n) =  O(logn)

    640?wx_fmt=png

    场景3:

    T(n) = 2

    只有常数量级,转化的时间复杂度为:

    T(n) =  O(1)

    640?wx_fmt=png

    场景4:

    T(n) = 0.5n^2 + 0.5n

    最高阶项为0.5n^2,省去系数0.5,转化的时间复杂度为:

    T(n) =  O(n^2)

    640?wx_fmt=png

    这四种时间复杂度究竟谁用时更长,谁节省时间呢?稍微思考一下就可以得出结论:

    O(1)< O(logn)< O(n)< O(n^2)

    在编程的世界中有着各种各样的算法,除了上述的四个场景,还有许多不同形式的时间复杂度,比如:

    O(nlogn), O(n^3), O(m*n),O(2^n),O(n!)

    今后遨游在代码的海洋里,我们会陆续遇到上述时间复杂度的算法。

    640?wx_fmt=png

     

    640?wx_fmt=png

    时间复杂度的巨大差异

     

     

    640?wx_fmt=jpeg

    640?wx_fmt=jpeg

    我们来举过一个栗子:

    算法A的相对时间规模是T(n)= 100n,时间复杂度是O(n)

    算法B的相对时间规模是T(n)= 5n^2,时间复杂度是O(n^2)

    算法A运行在小灰家里的老旧电脑上,算法B运行在某台超级计算机上,运行速度是老旧电脑的100倍。

    那么,随着输入规模 n 的增长,两种算法谁运行更快呢?

    640?wx_fmt=png

    从表格中可以看出,当n的值很小的时候,算法A的运行用时要远大于算法B;当n的值达到1000左右,算法A和算法B的运行时间已经接近;当n的值越来越大,达到十万、百万时,算法A的优势开始显现,算法B则越来越慢,差距越来越明显。

    这就是不同时间复杂度带来的差距。

    640?wx_fmt=jpeg

    如果感觉还不错,点个赞↗ 支持一下吧 ~

    随后还会不定期更新同类型文章,欢迎订阅关注我的博客 ~

    下一篇:400+条实用C/C++框架、库、工具整理 ,你能想到的都在这里了

    上一篇: Facebook前身 哈佛大学"选美"网站核心算法 -- ELO等级分制度(附源码)

    展开全文
  • 复杂度

    2019-11-04 11:10:47
    文章目录复杂度复杂度分析时间复杂度空间复杂度最好、最坏情况时间复杂度平均时间复杂度均摊时间复杂度 复杂度分析 数据结构和算法的目标:快、省,即执行效率和资源消耗。 “事后统计法”具有很大局限性,提前预估...

    复杂度

    复杂度分析

    1. 数据结构和算法的目标:快、省,即执行效率和资源消耗。
    2. “事后统计法”具有很大局限性,提前预估效率很重要。
    3. 复杂度分析是学习算法的精髓和分析算法的利器。

    时间复杂度

    1. 假设每行代码执行时间意义,所有代码的执行时间 T(n) 和每行代码的执行次数 n 成正比。
    T(n) = O (f(n))
    
    1. 大O时间复杂度表示代码执行效率随数据规模增长的变化趋势,也叫渐进时间复杂度
    2. 当n很大时,低阶、常量、系数并不左右增长趋势,可以省略,只需要记录最大量级。
    1. 只关注循环次数最多的一段代码.
    2. 加法法则:总复杂度等于量级最大的那一段代码。
    3. 乘法法则:嵌套代码的复杂度等于内外代码复杂度之积。
    1. 常见复杂度量级
      1. 非多项式量级:O(2n),O(n!)O(2^n),O(n!),称为NP算法,效率较低。
      2. 多项式量级:O(1),O(logn),O(n),O(nlogn),O(nk)O(1),O(logn),O(n),O(nlogn),O(n^k)

    O(1)O(1)

    int i = 1 ;
    int j = 2 ;
    int sum = i + j ;
    

    常量级时间复杂度的表示方法,即便有 3 行,也是 O(1) ,并非 O(3) 。一般情况下,只要不存在循环、递归,复杂度都为 O(1) ,与代码量无关。

    O(logn)O(nlogn)O(logn)、O(nlogn)

    int i = 1 ;
    while ( i <= n )
    {
        i = i * 2 ;
    }
    

    这段代码的复杂度为 O(log2n)O(log_2n),不同底数的对数可以互相转换,系数可以省略,所以统一表示为 O(logn)O(logn)
    O(nlogn)O(nlogn) 表示把 O(lognO(logn) 的代码循环执行n遍。

    O(n+m)O(nm)O(n+m)、O(n*m)

    T1(n) + T2(m) = O (f(n) + g(m))
    T1(n) * T2(m) = O (f(n) * g(m))
    

    当有多个数据规模,表示复杂度时不能省略。


    空间复杂度

    1. 大 O 空间复杂度表示代码存储空间随数据规模增长的变化趋势,也叫渐空间间复杂度
    void print(int n) 
    {
        int i = 0;
        int[] a = new int[n];
        for (i; i <n; ++i) 
        {
            a[i] = i * i;
        }
    }
    
    1. int[] a = new int[n]申请了大小为 n 的 int 类型数组,忽略常量阶的空间申请,所以上述代码空间复杂度为 O(n)。
    2. 常见的空间复杂度有O(1),O(n),O(n2)O(1),O(n),O(n^2);

    最好、最坏情况时间复杂度

    public int find(int[] array,int n,int x)
    {
        int p = -1 ;
        for(int i = 0 ; i < n ; ++i)
        {
            if(array[i] == x)
            {
                p = i ;
                break ;
            }
        }
        return p ;
    }
    /**
        上述代码的作用是返回数组中 x 出现的位置。
        最好:第一个就是要找-> O(1)
        最坏:遍历整个数组没有找到该元素-> O(n)
    **/
    
    1. 最好情况时间复杂度

    最理想情况下,执行这段代码的时间复杂度。

    1. 最坏情况时间复杂度

    最糟糕情况下,执行这段代码的时间复杂度。

    平均时间复杂度

    分析上述代码,在长度为n的数组中查询x的位置,有 n+1 种情况,分别为数组的 0 到 n-1 位置上和不在数组中,把每种情况下,需要遍历的元素个数累加起来,除以 n+1 ,得到需要遍历元素个数的平均值。

    1+2+3+...+n+nn+1=n(n+3)2(n+1) \frac{1+2+3+...+n+n}{n+1}\quad=\quad\frac{n(n+3)}{2(n+1)}

    忽略常量、系数、低阶,简化后时间复杂度为O(n);结果虽然正确,但是这样计算没有考虑每种情况发生的概率,正确计算过程如下:
    112n+212n+...+n12n+n12=3n+14 1*\frac{1}{2n}+2*\frac{1}{2n}+...+n*\frac{1}{2n}+n*\frac{1}{2}=\frac{3n+1}{4}
    此结果是加权平均值,平均时间复杂度即加权平均时间复杂度,简化后得 O(n)。

    均摊时间复杂度

    int[] array = new int[n];
    int count = 0;
    void insert(int val) 
    {
      if (count == array.length) 
      {
        int sum = 0;
        for (int i = 0; i < array.length; ++i) 
        {
          sum = sum + array[i];
        }
        array[0] = sum;
        count = 1;
      }
      array[count] = val;
      ++count;
    }
    

    这段代码实现了一个往数组中插入数据的功能。当数组满了之后,即 count == array.length 时,用 for 循环遍历数组求和,将求和之后的 sum 值放到数组的第一个位置,然后从第二个 位置开始插入数据。如果数组一开始就有空闲空间,则直接将数据插入数组

    分析以上代码,得出:

    1. 最好情况时间复杂度:有空闲位置,直接插入下标为 count 的位置,复杂度为 O(1)
    2. 最坏情况时间复杂度:遍历数组,复杂度为 O(n)
    3. 加权平均时间复杂度:有空闲位置 n 种情况,不空闲 1 种,概率都为1n+1\frac{1}{n+1},加权平均时间复杂度为 O(1)

    11n+1+11n+1+...+n1n+1=>O(1) 1*\frac{1}{n+1}+1*\frac{1}{n+1}+...+n*\frac{1}{n+1}=>O(1)

    1. 均摊时间复杂度是用摊还分析法得出的:

      例如上述代码中,每一次 O(n) 的插入操作,都会紧跟 n-1 个 O(1) 的插入操作,把耗时多的操作均摊到接下来 O(1) 的操作上,那么这一组操作的均摊时间复杂度就是 O(1)

      对一个数据结构进行一组连续操作中,大部分情况下时间复杂度都很低,只有个别情况下时间复杂度比较高,而且这些操作之间存在前后连贯的时序关系,这个时候,我们可以将这一组操作放在一起分析,看是否能将较高时间复杂度那次操作的耗时,平摊到其他那些时间复杂度比较低的操作上。

      在能够应用均摊时间复杂度分析的场合,一般均摊时间复杂度就等于最好情况时间复杂度

    展开全文
  • 时间复杂度是学习算法的基石,今天我们来聊聊为什么要引入时间复杂度,什么是时间复杂度以及如何去算一个算法的时间复杂度 一、刻画算法的运行时间 某日,慧能叫来了一尘打算给他补习补习一下基础知识,只见克写了...

    时间复杂度是学习算法的基石,今天我们来聊聊为什么要引入时间复杂度,什么是时间复杂度以及如何去算一个算法的时间复杂度

    一、刻画算法的运行时间

    某日,慧能叫来了一尘打算给他补习补习一下基础知识,只见克写了一段非常简单的代码

    图片

    image-20210426023110170

    image-20210426023130801

    image-20210426023148555

    image-20210426023211105

    图片

    image-20210426023246693

    image-20210426023310271

    一尘看老师有点生气,开始虚心请教了

    image-20210426023342540

    图片

    image-20210426023414239

    为了方便讨论,这里我们把每一条语句的执行时间都看做是一样的,记为一个时间单元

    image-20210426023526558

    图片

    image-20210426023557995

    ① 蓝色框的两条语句,花费两个时间单元

    ②黑色框的一条语句,花费n+1个时间单元

    ③红色框的两条语句,花费2*n个时间单元

    image-20210426023628861

    这不是数学吗,一尘心里想到

    image-20210426023704277

    其中的n被我们称为问题的规模,其实就是你处理问题的大小

    慧能顺手画了这个函数的图

    图片

    本文主要讨论问题规模和运行时间的关系,假定不同输入和运行时间基本无关

    image-20210426023934437

    image-20210426024024167

    image-20210426024046867

    image-20210426024103613

    image-20210426024120916

    二、时间复杂度

    image-20210426024201373

    比如说:T(n)=3n+3, 当n非常大的时候常数3和n的系数3对函数结果的影响就很小了

    图片

    image-20210426024250558

    比如:

    T(n)=n+1 忽略常数项 T(n)~n

    T(n)=n+n^2 忽略低阶项 T(n)~n^2

    T(n)=3n 忽略最高阶的系数 T(n)~n

    image-20210426024423010

    image-20210426024443197

    image-20210426024500918

    image-20210426024528079

    图片

    还好不用掌握那头疼的数学,一尘心中想到

    image-20210426024617355

    一尘把话题又拉了回来

    image-20210426024648521

    图片

    image-20210426024740873

    更准确地说O代表了运行时间函数的一个渐进上界,即T(n)在数量级上小于等于f(n)

    image-20210426024822915

    三、时间复杂度的计算

    image-20210426150816680

    一、得出运行时间的函数 二、对函数进行简化

    ①用常数1来取代运行时间中所有加法常数

    ②修改后的函数中,只保留最高阶项 ③如果最高阶项存在且不是1,则忽略这个项的系数

    image-20210426151026142

    图片

    image-20210426151057711

    O(1)也被称为常数阶

    image-20210426152505884

    image-20210426151148761

    图片

    image-20210426151218373

    image-20210426151246271

    一尘随手写了一段嵌套循环的代码

    图片

    image-20210426151329834

    image-20210426151350040

    image-20210426151412651

    图片

    接着,慧能又写了一段时间复杂度为对数的代码

    图片

    image-20210426151716075

    image-20210426151749173

    一向数学不太好的一尘此时有点懵

    image-20210426151639851

    图片

    image-20210426151926308

    image-20210426151945634

    image-20210426152009959

    image-20210426152029236

    image-20210423191506418

    总结

    算法的学习,第一步就是得先知道啥是时间复杂度,啥是空间复杂度,其实你懂了时间复杂度,也就懂了空间复杂度,建议各位还在校的小伙伴,一定要把数据结构和算法这门课学好。

    无论是面试还是提升自己的内容,算法学习基本少不了,我这里给大家推荐一份某 BAT 大佬总结的 Leetcode 刷题笔记:BAT 大佬分类总结的 Leetcode 刷题模版,助你搞定 90% 的面试

    另外,帅地也把排序算法系列文章用漫画写好了,这里直接贴出链接吧,你们负责收藏就好了,嘿嘿。不过这里只给出了 7 种必须掌握的排序算法,像桶排序,基数排序这些,了解即可,后期也会写出来滴。

    漫画:什么是冒泡排序算法?

    漫画:什么是选择排序算法?

    漫画:什么是插入排序算法?

    漫画:什么是希尔排序算法?

    漫画:什么是归并排序算法?

    漫画:什么是快速排序算法?

    漫画:什么是堆排序算法?

    当然,也欢迎大家来帅地的个人网站玩耍:https://www.iamshuaidi.com,从 0 到 1 总结了帅地的个人学习。

    作者简洁

    作者:大家好,我是帅地,从大学、自学一路走来,深知算法计算机基础知识的重要性,公众号「帅地玩编程」10万粉丝作者,专业于写这些底层知识,提升我们的内功,帅地期待你的关注,和我一起学习,点击了解我四年大学学 习之路 转载说明:未获得授权,禁止转载

    展开全文
  • 递归算法时间复杂度分析

    万次阅读 多人点赞 2018-09-17 16:16:59
    递归算法时间复杂度分析 时间复杂度: 一般情况下,算法中基本操作重复的次数就是问题规模n的某个函数f(n),进而分析f(n)随n的变化情况并确定T(n)的数量级。这里用‘o’来表示数量级,给出算法时间复杂度。 T...

                                 递归算法时间复杂度分析

    时间复杂度: 

    一般情况下,算法中基本操作重复的次数就是问题规模n的某个函数f(n),进而分析f(n)随n的变化情况并确定T(n)的数量级。这里用‘o’来表示数量级,给出算法时间复杂度。 
    T(n)=o(f(n)); 
    它表示随问题规模n的增大,算法的执行时间增长率和f(n)增长率成正比,这称作算法的渐进时间复杂度。而我们一般情况下讨论的最坏的时间复杂度。 
    空间复杂度: 
    算法的空间复杂度并不是实际占用的空间,而是计算整个算法空间辅助空间单元的个数,与问题的规模没有关系。算法的空间复杂度S(n)定义为该算法所耗费空间的数量级。 
    S(n)=o(f(n)) 
    若算法执行所需要的辅助空间相对于输入数据n而言是一个常数,则称这个算法空间复杂度辅助空间为o(1); 
    递归算法空间复杂度:递归深度n*每次递归所要的辅助空间,如果每次递归所需要的辅助空间为常数,则递归空间复杂度o(n)。

    递归算法分析

    1、利用数列知识

    1. 累加法:递推关系式为an+1−an=f(n)an+1−an=f(n)采用累加法。
    2. 累乘法:递推关系式为an+1an=f(n)an+1an=f(n)采用累乘法。
    3. 构造法:递推关系式为(1)aa+1=pan+qaa+1=pan+q,(2)aa+1=pan+qnaa+1=pan+qn,都可以通过恒等变形,构造出等差或等比数列,利用等差或等比数列的定义进行解题,其中的构造方法可通过待定系数法来进行。
    4. 和化项法:递推公式为Sn=f(n)Sn=f(n)或Sn=f(an)Sn=f(an)一般利用

      an={S1,Sn−Sn−1,当n=1当n>=2an={S1,当n=1Sn−Sn−1,当n>=2

    5. 用特征方程求解递推方程(感觉比较生僻,不做解释)
    6. 迭代法: 从原始递推方程开始,反复将对于递推方程左边的函数用右边的等式代入,直到得到初值,然后将所得的结果进行化简。 
      例如在调用归并排序mergeSort(a,0,n-1)对数组a[0...n−1]a[0...n−1]排序时,执行时间T(n)T(n)的递推关系式为:

      T(n)={O(1),2T(n2)+O(n),当n=1当n>=2T(n)={O(1),当n=12T(n2)+O(n),当n>=2


      其中,O(n)O(n)为merge()所需要的时间,设为cncn(c为正常量)。因此: 

      T(n)=2T(n2)+cn=2(2T(n4)+cn2)+cn=22T(n4)+2cn=23T(n8)+3cn=...=2kT(n2k)+kcn=nO(1)+cnlog2n=O(nlog2n),(假设n=2k,则k=log2n)T(n)=2T(n2)+cn=2(2T(n4)+cn2)+cn=22T(n4)+2cn=23T(n8)+3cn=...=2kT(n2k)+kcn=nO(1)+cnlog2⁡n=O(nlog2⁡n),(假设n=2k,则k=log2⁡n)


      忽略求解细节。在我们求解递归式时,因为最终是要求得一个时间上限,所以在求解时常常省略一些细节。比如mergeSort(a,0,n-1)运行时间的实际递归式应该是: 

    T(n)={O(1),T(⌈n2⌉)+T(⌊n2⌋)+O(n),当n=1当n>=2T(n)={O(1),当n=1T(⌈n2⌉)+T(⌊n2⌋)+O(n),当n>=2


    但我们忽略这些上取整、下取整以及边界条件,甚至假设问题规模n=2kn=2k,这都是为方便求解而忽略的细节。经验和一些定理告诉我们,这些细节不会影响算法时间复杂度的渐近界。

     

      类似的,我们也可以用迭代法求解汉诺塔递归求解时的时间复杂度。但遗憾的是,迭代法一般适用于一阶的递推方程。对于二阶及以上(即T(n)依赖它前面更多个递归项T(n)依赖它前面更多个递归项)的递推方程,迭代法将导致迭代后的项太多,从而使得求和公式过于复杂,因此需要将递推方程化简,利用差消法等技巧将高阶递推方程化为一阶递推方程。如在求快速排序算法平均时间复杂度T(n)T(n)的递推方程,T(n)T(n)依赖T(n−1)、T(n−2)、...、T(1)T(n−1)、T(n−2)、...、T(1)等所有的项,这样的递推方程也称为全部历史递推方程。(这里省略快速排序算法平均复杂度T(n)的求解过程)

    小结:上面6种递推关系是高中、本科知识,在此重点介绍了迭代法,其它几种方法虽未在本篇中使用,但可以加深对递推式求解的认识。


    2、代入法

    代入法实质上就是数学归纳法,因此求递推式分为两步:

    1. 猜测解的形式;
    2. 用数学归纳法求出解中的常数,并证明解是正确的。

      遗憾的是并不存在通用的方法来猜测递归式的正确解,需要凭借经验,偶尔还需要创造力。即使猜出了递归式解的渐近界,也有可能在数学归纳证明时莫名其妙的失败。正是由于该方法技术细节较为难掌握,因此这个方法不适合用来求解递归方程,反而比较适合作为其他方法检验手段。在此不做总结。可以翻阅《算法导论》进行学习。


    3、递归树

      递归树是一棵结点带权值的树。初始的递归树只有一个结点,它的权标记为T(n)T(n);然后按照递归树的迭代规则不断进行迭代,每迭代一次递归树就增加一层,直到树中不再含有权值为函数的结点(即叶结点都为T(1)T(1))。下面以递归方程

    T(n)={O(1),2T(n2)+O(n),当n=1当n>=2;(假设n=2k,则k=log2n)T(n)={O(1),当n=12T(n2)+O(n),当n>=2;(假设n=2k,则k=log2⁡n)

    来讲述递归树的迭代规则。

     

    • 第一步: 把根结点T(n)T(n)用根是cncn、左结点为T(n2)T(n2)、右结点为T(n2)T(n2)的子树代替(即:以分解、合并子问题需要的代价为根,分解得到的子问题为叶的子树。其中常量c代表求解规模为1的问题所需的时间);(如下如(a)→(b)(a)→(b))
    • 第二步:把叶结点按照“第一步”的方式展开;T(n2)T(n2)用根是cn/2cn/2、左节点为T(n4)T(n4)、右结点为T(n4)T(n4)的子树代替。(如下如(b)→(c)(b)→(c))
    • 第三步:反复按照“第一步”的方式迭代,每迭代一次递归树就增加一层,直到树中不再含有权值为函数的结点(即叶结点都为T(1)T(1))。(如下如(c)→(d)(c)→(d))

     

    这里写图片描述

     

      在得到递归树后,将树中每层中的代价求和,得到每层代价,然后将所有层的代价求和,得到所有层次的递归调用的总代价。在上图(d)部分中,完全展开的递归树高度为lgnlg⁡n(树高为根结点到叶结点最长简单路径上边的数目),所有递归树具有lgn+1lg⁡n+1层,所以总代价为cn∗(lgn+1)cn∗(lg⁡n+1),所有时间复杂度为Θ(nlgn)Θ(nlg⁡n)。

      总结:递归树模型求解递归方程,本质上就是迭代思想的应用,利用递归方程迭代展开过程构造对应的递归树,然后把每层的时间代价进行求和。不过递归树模型更直观,同时递归树也克服了二阶及更高阶递推方程不方便迭代展开的痛点。


    4、主方法求解递推式

      主方法为如下形式的递归式提供了一种“菜谱”式的求解方法,如下所示 

    T(n)=aT(n/b)+f(n)T(n)=aT(n/b)+f(n)

     

    其中a≥1a≥1和b>1b>1是常数,f(n)f(n)是渐近正函数。这个递推式将规模为n的问题分解为a个子问题,每个子问题的规模为n/bn/b,a个子问题递归地求解,每个花费时间T(n/b)T(n/b)。函数f(n)f(n)包含了问题分解和子问题解合并的代价。同样,这个递归式也没有考虑上取整、下取整、边界条件等,结果不会影响递归式的渐近性质。

    定理4.1(主定理) 令a≥1和b>1是常数,f(n)f(n)是一个函数,T(n)T(n)是定义在非负整数上的递归式: 

    T(n)=aT(n/b)+f(n)T(n)=aT(n/b)+f(n)


    其中我们将n/bn/b解释为⌊n/b⌋⌊n/b⌋或⌈n/b⌉⌈n/b⌉。那么T(n)T(n)有如下渐近界: 
    1. 若对某个常数ε>0ε>0有f(n)=O(n(logba)−ε)f(n)=O(n(logb⁡a)−ε),则T(n)=Θ(nlogba)T(n)=Θ(nlogb⁡a) 
    2. 若f(n)=Θ(nlogba)f(n)=Θ(nlogb⁡a),则T(n)=Θ(nlogbalgn)T(n)=Θ(nlogb⁡alg⁡n)。 
    3. 若对某个常数ε>0ε>0有f(n)=Ω(n(logba)+ε)f(n)=Ω(n(logb⁡a)+ε),且对某个常数c<1c<1和所有足够大的n有af(n/b)≤cf(n)af(n/b)≤cf(n),则T(n)=Θ(f(n))T(n)=Θ(f(n))

     

      在使用主定理之前,要比较f(n)和(nlogba)f(n)和(nlogb⁡a)的大小,这个大小不是算术意义上的大小比较,而是要在多项式意义上比较。以上三种情况在多项式意义上并未覆盖f(n)f(n)的所有可能性。情况1和情况2之间有一定间隙;情况2和情况3之间也有一定间隙。如果f(n)落在这两个间隙中,或者情况3中 正则条件不成立,就不能使用主方法来求递归式。 
      如在递归式:T(n)=2T(n/2)+nlgnT(n)=2T(n/2)+nlg⁡n中,因为 nlogba=n<f(n)=nlgnnlogb⁡a=n<f(n)=nlg⁡n,但是f(n)f(n)并不大于n一个多项式因子nεnε ,因为对于给定的ε>0ε>0当n足够大时,均有nε>lgnnε>lg⁡n。所以找不到这样 ε>0ε>0,该递归式落入了情况2和情况3之间的间隙,不能使用主定理。 
      最后给出主定理应用的几个练习题:

     

    主方法联系

    具体举例分析:

    【代入法】代入法首先要对这个问题的时间复杂度做出预测,然后将预测带入原来的递归方程,如果没有出现矛盾,则是可能的解,最后用数学归纳法证明。

      【举   例】我们有如下的递归问题:T(n)=4T(n/2)+O(n),我们首先预测时间复杂度为O(n2),不妨设T(n)=kn2(其中k为常数),将该结果带入方程中可得:左=kn2,右=4k(n/2)2+O(n)=kn2+O(n),由于n2的阶高于n的阶,因而左右两边是相等的,接下来用数学归纳法进行验证即可。


       【迭代法】迭代法就是迭代的展开方程的右边,直到没有可以迭代的项为止,这时通过对右边的和进行估算来估计方程的解。比较适用于分治问题的求解,为方便讨论起见,给出其递归方程的一般形式:

      【举   例】下面我们以一个简单的例子来说明:T(n)=2T(n/2)+n2,迭代过程如下:

      容易知道,直到n/2^(i+1)=1时,递归过程结束,这时我们计算如下:

      到这里我们知道该算法的时间复杂度为O(n2),上面的计算中,我们可以直接使用无穷等比数列的公式,不用考虑项数i的约束,实际上这两种方法计算的结果是完全等价的,有兴趣的同学可以自行验证。


    【公式法】这个方法针对形如:T(n) = aT(n/b) + f(n)的递归方程。这种递归方程是分治法的时间复杂性所满足的递归关系,即一个规模为n的问题被分成规模均为n/b的a个子问题,递归地求解这a个子问题,然后通过对这a个子问题的解的综合,得到原问题的解。这种方法是对于分治问题最好的解法,我们先给出如下的公式:

      公式记忆:我们实际上是比较n^logba和f(n)的阶,如果他们不等,那么T(n)取他们中的较大者,如果他们的阶相等,那么我们就将他们的任意一个乘以logn就可以了。按照这个公式,我们可以计算【迭代法】中提到的例子:O(f(n))=O(n2),容易计算另外一个的阶是O(n),他们不等,所以取较大的阶O(n2)。太简单了,不是吗?

      需要注意:上面的公式并不包含所有的情况,比如第一种和第二种情况之间并不包含下面这种情况:f(n)是小于前者,但是并不是多项式的小于前者。同样后两种的情况也并不包含所有的情况。为了好理解与运用的情况下,笔者将公式表述成如上的情况,但是并不是很严谨,关于该公式的严密讨论,请看这里。但是公式的不包含的情况,我们很少很少碰到,上面的公式适用范围很广泛的。

      特别地,对于我们经常碰到的,当f(n)=0时,我们有:


    【母函数法】母函数是用于对应于一个无穷序列的幂级数。这里我们解决的递归问题是形如:T(n)=c1T(n-1)+c2T(n-2)+c3T(n-3)+...+ckT(n-k)+f(n)。为说明问题简便起见,我们选择斐波那契数列的时间复杂度作为例子进行讨论。

      【举  例】斐波那契数列递归公式:T(n)=T(n-1)+T(n-2)。这里我们假设F(n)为第n项的运算量。则容易得到:F(n)=F(n-1)+F(n-2),其中F(1)=F(2)=1.我们构造如下的母函数:G(x)=F(1)x+F(2)x2+F(3)x3+......,我们可以推导如下:

      上面的方法计算相对来说是比较简单的,关键在于对于母函数的理解,刚开始的时候可能不是很好理解,对于母函数可以参考这里维基百科这里


    【差分方程法】可以将某些递归方程看成差分方程,通过解差分方程的方法来解递归方程,然后对解作出渐近阶估计。这里我们只考虑最长常见的递归形式,形如:T(n)=c1T(n-1)+c2T(n-2)+c3T(n-3)+...+ckT(n-k)+f(n),其中c1,c2,...ck为常数且不等于0;我们对该方程的求解如下:

      对应上面的齐次方程的特征方程为:

      如果解得t=r是该特征方程的m重根,则这m个解的形式为:{rn     n*rn      n2rn   ...    nm-1rn},其余的关于复数解的形式和普通的线性方程组的形式类似,不再赘述。接下来,我们要求解该方程的对应非齐次方程组的通解,这里我们针对该方程的特殊形式,不加证明地给出如下的通解形式:

      则和线性代数中的解一样,原方程的解等于齐次方程组的通解+特解,即:

      最后由初始条件确定a(i)的值即可。

      为了帮助理解,我们举两个例子看看,就明白是怎么回事了。

      【举 例1】递归方程如下:

    (1)写出对应齐次方程的特征方程:

    得到基础解系为:{t1n,  t2n}

    (2)计算特解,对于本题,直接观察得特解为:-8

    (3)得到原方程解的形式为:T(n)=a0t1n+a1t2n-8

    (4)代入n=0,n=1的情况,得到a0,a1,最后可得:

      可以看到该方程形式和上面讨论过的斐波那契数列只差一个常数8,因而两者的时间复杂度是相同的。有兴趣的同学可以按照这个方法再次计算斐波那契数列的时间复杂度验证一下。

      【举  例2】递归方程如下:

    (1)计算对应齐次方程的基础解析:特征方程为:C(t)=t^2-4t-4=0,得到一个2重根t=2.因而其基础解为:{2n      n*2n}

    (2)由于f(n)=n*2n,对应上面表格的最后一种情况,得到特解形式为:T(n)=n2(p0+p1n)2n代入原递归方程可得:p0=1/2,p1=1/6

    (3)原方程解的形式为:T(n)=a0*2n+a1*n*2n+n2(1/2+n/6)2n,代入T(0),T(1)得:a0=a1=0

    (4)综上:T(n)=n2(1/2+n/6)2n

    因而时间复杂度为:O(n32n).

     

    参考:https://blog.csdn.net/so_geili/article/details/53444816

              https://blog.csdn.net/m0_37734999/article/details/78751882

              https://www.cnblogs.com/hlongch/p/5749038.html

    展开全文
  • 时间复杂度和空间复杂度的简单讲解

    万次阅读 多人点赞 2018-01-07 12:55:26
    一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。 把今年很流行,淡淡的基佬紫送给各位看官,原谅绿就算了,怕被打死...当我们面前有多个算法时,我们可以通过计算时间复杂度,判断出哪一
  • 算法的时间复杂度和空间复杂度-总结

    万次阅读 多人点赞 2013-09-20 16:01:26
    算法的时间复杂度和空间复杂度 1、时间复杂度 (1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的...
  • 时间复杂度复杂度讲的清清楚楚!
  • 时间复杂度

    2018-08-01 11:13:06
    时间复杂度时间复杂度时间复杂度时间复杂度时间复杂度时间复杂度时间复杂度时间复杂度时间复杂度时间复杂度时间复杂度时间复杂度时间复杂度时间复杂度时间复杂度时间复杂度时间复杂度时间复杂度时间复杂度时间复杂度...
  • 简析时间复杂度和空间复杂度

    万次阅读 多人点赞 2019-06-25 16:24:17
    时间复杂度和空间复杂度是用来评价算法效率高低的2个标准,身为开发者肯定会经常会听到这2个概念,但它们分别是什么意思呢? 其实这两个概念从字面意思上也能看出一二: 时间复杂度:就是说执行算法需要消耗的时间...
  • 算法的时间与空间复杂度(一看就懂)

    万次阅读 多人点赞 2018-11-21 11:17:45
    算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,... 时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述。 空间维度:是指执行当前算...
  • 时间复杂度 常数复杂度 O(1) 对数复杂度 O(log n) 线性复杂度 O(n) 平方复杂度 O(n^2) 立方复杂度 O(n^3) 指数复杂度 O(2^n) 阶乘复杂度 O(n!) 工程代码要求做法: 1:每写完一段代码下意识的检测计算下时间和空间...
  • 时间复杂度和空间复杂度

    万次阅读 多人点赞 2017-05-15 20:38:47
    算法复杂度分为时间复杂度和空间复杂度。 其作用: 时间复杂度是指执行算法所需要的计算工作量; 而空间复杂度是指执行这个算法所需要的内存空间。 (算法的复杂性体现在运行该算法时的计算机所需资源的多少上,...
  • 算法复杂度分为时间复杂度和空间复杂度。 时间复杂度用于度量算法执行的时间长短;而空间复杂度则是用于度量算法所需存储空间的大小。 目录 时间复杂度 1.时间频度 2.计算方法 3.分类 空间复杂度 算法的时间...
  • 一看就懂:时间复杂度与空间复杂度

    千次阅读 多人点赞 2019-07-23 15:06:03
    那么在代码里,耗时多少则用时间复杂度表示,占用的内存多少则可以用空间复杂度表示。 本文只做简单介绍,让不明白的同学明白这两个概念,并不深入。 【时间复杂度】 (1)什么是时间复杂度? 书面的语言不用...
  • 本次学习的三大目标: .搞清楚时间、空间复杂度的概念。...时间、空间复杂度都是越小效率越高,通常所说的复杂度都是指时间复杂度。 2.计算时间、空间复杂度 时间复杂度计算 推导大O阶有一下三种规则: 1.用
  • 时间复杂度、空间复杂度,如果要严格意义的数学证明的话,公式比较繁复,这些公式很让人头疼,我们简单地通过读程序来判断时间复杂度。 时间复杂度的表达: Big O notation 常见的7种时间复杂度: O(1):Constant...
  • 时间复杂度 算法中基本操作重复执行的次数是问题规模n的某个函数f(n),分析f(n)随n的变化情况并确定T(n)的数量级,用”O”表示数量级,来给出算法的时间复杂度。 T(n) = O(f(n)) 该式表示随着问题规模n的增大,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 229,732
精华内容 91,892
关键字:

复杂度