精华内容
下载资源
问答
  • 复杂度分析
    2022-04-17 23:46:13

    一、什么是复杂度分析?

    1.数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。

    2.因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。

    3.分别用时间复杂度和空间复杂度两个概念来描述性能问题,二者统称为复杂度。

    4.复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。

    二、为什么要进行复杂度分析?

    1.和性能测试相比,复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。

    2.掌握复杂度分析,将能编写出性能更优的代码,有利于降低系统开发和维护成本。

    三、如何进行复杂度分析?

    1.大O表示法

    1)来源 算法的执行时间与每行代码的执行次数成正比,用T(n) = O(f(n))表示,其中T(n)表示算法执行总时间,f(n)表示每行代码执行总次数,而n往往表示数据的规模。

    2)特点 以时间复杂度为例,由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势,所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响,所以在做时间复杂度分析时忽略这些项。

    2.复杂度分析法则

    1)单段代码看高频:比如循环。

    2)多段代码取最大:比如一段代码中有单循环和多重循环,那么取多重循环的复杂度。

    3)嵌套代码求乘积:比如递归、多重循环等

    4)多个规模求加法:比如方法有两个参数控制两个循环的次数,那么这时就取二者复杂度相加。

    四、常用的复杂度级别?

    多项式阶:随着数据规模的增长,算法的执行时间和空间占用,按照多项式的比例增长。包括, O(1)(常数阶)、O(logn)(对数阶)、O(n)(线性阶)、O(nlogn)(线性对数阶)、O(n^2)(平方阶)、O(n^3)(立方阶)

    非多项式阶:随着数据规模的增长,算法的执行时间和空间占用暴增,这类算法性能极差。包括, O(2^n)(指数阶)、O(n!)(阶乘阶)

    五、如何掌握好复杂度分析方法?

    复杂度分析关键在于多练,所谓孰能生巧。

    更多相关内容
  • textComplexityAnalyzer:文本复杂度分析器(子句和短语的复杂度)
  • 本文阐述了遗传禁忌搜索算法的混合策略,从理论上对该算法的收敛性进行了证明,对时间复杂度进行了分析。应用马尔科夫链模型证明了遗传禁忌搜索算法是以概率1收敛到全局最优解的,并应用求解随机算法时间复杂度的方法,...
  • 基于Python和Coh-Metrix高考英语“一年两考”阅读文本复杂度分析.pdf
  • 主要介绍了Java针对封装数组的简单复杂度分析方法,简单讲述了java封装数组时间复杂度分析的原理、实现方法与操作注意事项,需要的朋友可以参考下
  • 对时间复杂度和空间复杂度进行超级详细的讲解
  • 算法复杂度分析

    千次阅读 2021-03-30 08:21:19
    复杂度分析用来做什么?   当我们设计一个算法的时候,我们希望让设计的代码运行的更快,更省内存。但是如何考量以上两个指标呢?我们需要通过时间、空间复杂度分析的方式来进行考量。复杂度分析对算法来说非常的...

    复杂度分析用来做什么?

      当我们设计一个算法的时候,我们希望让设计的代码运行的更快,更省内存。但是如何考量以上两个指标呢?我们需要通过时间、空间复杂度分析的方式来进行考量。复杂度分析对算法来说非常的重要,也是整个算法学习的精髓。

      复杂度也叫渐进复杂度,包括时间复杂度和空间复杂度,用来分析算法执行效率与数据规模之间的增长关系,可以粗略地表示,越高阶复杂度的算法,执行效率越低。常见的复杂度并不多,从低阶到高阶有:O(1)、O(logn)、O(n)、O(nlogn)、O(n2 )。

    在这里插入图片描述

    为什么要做复杂度分析?

      当然,我们写完之后把代码跑一遍,也能得到算法损耗的时间以及存储空间(像力扣刷题一样)。

    我们做数据分析真的能比把代码跑一遍准确吗?

      首先,把代码跑一遍的评估方法是正确的,一些书籍将其称作事后统计法。但是,这些方法拥有局限性。局限性体现在以下方面。

    1. 测试结果高度依赖于测试环境

      测试环境中硬件的不同(处理器i9比i3快很多)将影响测试结果。我们也许会遇到在某台处理器上代码a比代码b快,换一台处理器结果就会反过来的情况。

    1. 测试结果受数据规模影响更大

      对同一个排序算法,待排序数据的有序度不一样,排序的执行时间就会有很大的差别。(排序算法,如果用例本身有序那么什么都不用做)
      如果测试数据规模太小,测试结果可能无法真实地反映算法的性能(比如,对于小规模的数据排序,插入排序可能反倒会比快速排序要快)。
      如果测试数据体量太大(达到TB级或者PB级),简单的一个wordCount操作也需要大数据生态的数据处理组件来解决。

    复杂度分析表示方法

    O复杂度表示法

      从CPU的角度看,我们程序的每一行都在执行着读数据-运算-写数据的操作。尽管每行代码对应的cpu的执行个数及时间都不一样,但是由于我们现在讨论的没有那么精准,所以假设每行代码执行时间都一样。我们假设这个值为time。

    有段代码用来求数从1到n的累加和,代码如下:

    
     int cal(int n) {
       int sum = 0;
       int i = 1;
       for (; i <= n; ++i) {
         sum = sum + i;
       }
       return sum;
     }
    

      由以上代码可以看出,在for循环前的代码每行执行了一遍,在for循环及其中的代码每行执行了n遍,那么总消耗时间为(2+2n)*time,可以看出,所有代码的时间消耗T(n)与每行代码的执行次数成正比(代码行数越多,执行时间越长)。
      这种正比的关系,我们可以按照O表示法来表示。

    • n用来表示数据规模的大小
    • f(n)表示代码执行次数的总和
    • O用来表示正比的关系

    那么以上代码块的正比关系可以用T(n) = O(2n+2)来表示。

      这里的O表示法并不表示代码真正的执行时间,而是表示一种代码执行时间随着数据规模增长的变化趋势,也叫渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

      由于公式中的常量、系数和低阶并不左右这种对应关系的增长趋势,所以我们只记一个最大量级即可。即T(n) = O(n)。

    如何分析一段代码的时间复杂度?三个方法

    1.只关注执行次数最多的一段代码

      我们在分析一个算法、一段代码的时间复杂度的时候,也只关注循环执行次数最多的那一段代码就可以了(由于常量,低阶和系数在O时间复杂度表示法中可省略,因为它们量级低,执行次数最多的一段代码才会是高量级)。

    2.加法法则:总复杂度等于量级最大的那段代码的复杂度

      执行次数是n次的代码和执行次数是n²的代码在一起,总的复杂度是O(n²)。因为当n无限大的时候,n的时间复杂度可以省略,因为它对正比对应关系的趋势没影响。

    加法法则对应成公式的形式:如果 T1(n)=O(f(n)),T2(n)=O(g(n));那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n))).

    3. 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

    乘法法则是一个嵌套循环的情况:

    
    int cal(int n) {
       int ret = 0; 
       int i = 1;
       for (; i < n; ++i) {
         ret = ret + f(i);
       } 
     } 
     
     int f(int n) {
      int sum = 0;
      int i = 1;
      for (; i < n; ++i) {
        sum = sum + i;
      } 
      return sum;
     }
    

      上面的循环,T1(n) = O(n),但f()方法内还有一个循环,T2(n) = O(n)。总体的时间复杂度需要进行一个乘法运算,即T(n) = T1(n) * T2(n) = O(n*n) = O(n2)。

    常见的时间复杂度的量级

    常见的时间复杂度的量级分为两种:

    • 多项式量级(左侧),这类能找到多项式级时间复杂度的解决算法的问题叫做P(Deterministic )问题
    • 非多项式量级(右侧),这类解决它的时间复杂度为非多项式量级的算法问题叫作 NP(Non-Deterministic Polynomial,非确定多项式)问题。
      在这里插入图片描述
        当数据规模 n 越来越大时,非多项式量级算法的执行时间会急剧增加,求解问题的执行时间会无限增长。所以,非多项式时间复杂度的算法其实是非常低效的算法。
    常量阶O(1)

      O(1) 只是常量级时间复杂度的一种表示方法,并不是指只执行了一行代码。,只要代码的执行时间不随 n 的增大而增长,这样代码的时间复杂度我们都记作 O(1)。或者说,一般情况下,只要算法中不存在循环语句、递归语句,即使有成千上万行的代码,其时间复杂度也是Ο(1)。比如,哈希查找

    O(logn)、O(nlogn)

      对数阶非常的常见,从我们的快排,归并,到我们的二分查找都有涉及。

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

      以上代码可以看到,循环中的行执行次数是最多的,我们可以看出,它的执行次数取决于n的大小。具体的执行过程如下:

    • i从1开始,进入循环
    • 每循环一次,i的值都会进行*2的操作
    • 直到i的值大于n,那么退出循环

    由以上的过程可以看出,i的取值是一个等比数列,如下:
    在这里插入图片描述
    我们只需要知道上图中的x是多少,就可以得到循环中间那行代码的执行次数。

      求解 x 这个问题我们通过高中时期的指数对数运算方法可以得到,x=log2n,所以,这段代码的时间复杂度就是 O(log2n)。

      那么,如果中间是以3为底呢?如果是以100为底呢?

    我们可以把所有对数阶的时间复杂度都记为 O(logn)。

    对数之间是可以互相转换的,我们可以通过对数的换底公式得到,
    在这里插入图片描述

    log3n 就等于 log 3²* log2n,所以 O(log3n) = O(C * log2n),其中 C=log 3² 是一个常量。

    O(m+n)、O(m*n)–由两个数据规模来决定的时间复杂度
    
    int cal(int m, int n) {
      int sum_1 = 0;
      int i = 1;
      for (; i < m; ++i) {
        sum_1 = sum_1 + i;
      }
    
      int sum_2 = 0;
      int j = 1;
      for (; j < n; ++j) {
        sum_2 = sum_2 + j;
      }
    
      return sum_1 + sum_2;
    }
    

      从代码中可以看出,m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大,所以我们在表示复杂度的时候,就不能简单地利用加法法则,省略掉其中一个。所以,上面代码的时间复杂度就是 O(m+n)

      针对这种情况,原来的加法法则就不正确了,我们需要将加法规则改为:T1(m) + T2(n) = O(f(m) + g(n))。
      但是乘法法则继续有效:T1(m)*T2(n) = O(f(m) * f(n))。

    空间复杂度分析

    • 时间复杂度的全称是渐进时间复杂度,表示算法的执行时间与数据规模之间的增长关系
    • 空间复杂度全称就是渐进空间复杂度(asymptotic space complexity),表示算法的存储空间与数据规模之间的增长关系。
    
    void print(int n) {
      int i = 0;
      int[] a = new int[n];
      for (i; i <n; ++i) {
        a[i] = i * i;
      }
    
      for (i = n-1; i >= 0; --i) {
        print out a[i]
      }
    }
    

    分析:第 2 行代码中,我们申请了一个空间存储变量 i,但是它是常量阶的,跟数据规模 n 没有关系,所以我们可以忽略。第 3 行申请了一个大小为 n 的 int 类型数组,除此之外,剩下的代码都没有占用更多的空间,所以整段代码的空间复杂度就是 O(n)。

    我们常见的空间复杂度就是 O(1)、O(n)、O(n2 ),像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。

    针对不同输入情况下复杂度量级不同:时间复杂度分析(最好,最坏,平均,均摊)

    最好,最坏时间复杂度分析

    先看个例子:

    以下代码用来暴力查找数组中元素x的位置,如果不存在则返回-1

    
    // n表示数组array的长度
    int find(int[] array, int n, int x) {
      int i = 0;
      int pos = -1;
      for (; i < n; ++i) {
        if (array[i] == x) pos = i;
      }
      return pos;
    }
    

      从我们上文描述的方法得知,这段代码的时间复杂度是O(n),空间复杂度也是O(n)。
      但是这样查找的方式不够高效,因为我们需要全部遍历一遍才能退出这个查找方法。事实上,我们找到对应的元素之后就可以直接退出了。我们可以对这段代码优化如下:

    
    // n表示数组array的长度
    int find(int[] array, int n, int x) {
      int i = 0;
      int pos = -1;
      for (; i < n; ++i) {
        if (array[i] == x) {
           pos = i;
           break;
        }
      }
      return pos;
    }
    

    加一个判断之后,时间复杂度还是O(n)吗?显然不是了。
    因为,要查找的变量 x 可能出现在数组的任意位置。所以,不同的情况下,这段代码的时间复杂度是不一样的。

    最好情况时间复杂度(best case time complexity)

      最好情况时间复杂度就是,在最理想的情况下,执行这段代码的时间复杂度。就像我们刚刚讲到的,在最理想的情况下,要查找的变量 x 正好是数组的第一个元素,这个时候对应的时间复杂度就是最好情况时间复杂度。

    最坏情况时间复杂度(worst case time complexity)

      最坏情况时间复杂度就是,在最糟糕的情况下,执行这段代码的时间复杂度。就像刚举的那个例子,如果数组中没有要查找的变量 x,我们需要把整个数组都遍历一遍才行,所以这种最糟糕情况下对应的时间复杂度就是最坏情况时间复杂度。

    最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度,发生的概率其实并不大。

    平均情况时间复杂度(average case time complexity)

    平均情况时间复杂度就是平均情况下要遍历多少个元素的值吗?

    平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。

    我们先按照这样算一下:

    • 要查找的变量 x 在数组中的位置,有 n+1 种情况:在数组的 0~n-1 位置中和不在数组中。
    • 需要遍历的元素个数的平均值:我们把每种情况下查找需要遍历的元素个数累加起来,然后再除以 n+1

    在这里插入图片描述
    我们知道,时间复杂度的大 O 标记法中,可以省略掉系数、低阶、常量,所以,咱们把刚刚这个公式简化之后,得到的平均时间复杂度就是 O(n)。

    结论是正确的但是,这样的分析方式是不严谨的,因为这 n+1 种情况,出现的概率并不是一样的。

    • 要查找的变量 x,要么在数组里,要么就不在数组里。为了方便理解,我们假设在数组中与不在数组中的概率都为 1/2。
    • 另外,要查找的数据出现在 0~n-1 这 n 个位置的概率也是一样的,为 1/n。所以,根据概率乘法法则,要查找的数据出现在 0~n-1中任意位置的概率就是 1/(2n)。

    在这里插入图片描述

      这个值就是概率论中的加权平均值,也叫作期望值,所以**平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。引入概率之后,前面那段代码的加权平均值为 (3n+1)/4。**用大 O 表示法来表示,去掉系数和常量,这段代码的加权平均时间复杂度仍然是 O(n)。

      很多时候,我们使用一个复杂度就可以满足需求了。只有同一块代码在不同的情况下,时间复杂度有量级的差距,我们才会使用这三种复杂度表示法来区分。
    均摊时间复杂度(amortized time complexity)

    均摊时间复杂度就是一种特殊的平均时间复杂度

      大部分情况下,我们并不需要区分最好、最坏、平均三种复杂度。平均复杂度只在某些特殊情况下才会用到,而均摊时间复杂度应用的场景比它更加特殊、更加有限。

    举个例子,有插入代码如下,用来插入数据:

    1. 当数组不满的时候直接插入
    2. 当数组满的时候计算数组元素的总和,并将数组的元素逻辑移除,将总和的值置入第一个元素。
    
     // array表示一个长度为n的数组
     // 代码中的array.length就等于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;
     }
    

    以上这段代码的最好,最坏,平均时间复杂度分析如下:

    1. 最好的时间复杂度为O(1)即数组不满的时候直接插入;最坏的时间复杂度为O(n)j即数组满了,要求和再插入。
    2. 加权平均的时间复杂度是O(n):根据插入位置的不同,分为n种情况:1到n-1位置时间复杂度是1,n位置时间复杂度是n,这n+1种情况发生的概率都是一样的,所以时间复杂度为:

    在这里插入图片描述
    均摊时间复杂度的运用场景

    1. 对一个数据结构进行一组连续操作中,大部分情况下时间复杂度都很低,只有个别情况下时间复杂度比较高
    2. 而且这些操作之间存在前后连贯的时序关系(比如一个 O(n) 插入之后,紧跟着 n-1 个 O(1) 的插入操作)
    摊还分析

    遇到以上场景的时候,我们可以把这一组操作放在一起分析,看是否能看是否能将较高时间复杂度那次操作的耗时,平摊到其他那些时间复杂度比较低的操作上

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

    复杂度分析的应用–快排

    以下是我手敲的一段快排代码
    快排核心部分分为三个步骤:

    1. 找到固定位置(这里取的是left边界的位置)的值(flag)应该放在的位置(当l=r的位置),将小于它的都放左边,大于它的都放右边
    2. 将找到的位置放入固定值flag
    3. 递归以上操作,排该位置左边的元素,排该位置右边的元素
    class Solution {
        public int[] sortArray(int[] nums) {
            int left = 0;
            int right = nums.length-1;
            mySort(nums,left,right);
            return nums;
        }
            private void mySort(int[] nums, int left, int right) {
            int l = left;
            int r = right;
            if(l<r){
                int flag = nums[l];
                while(l<r){
                    while(l<r&&nums[r]>=flag) r--;
                    nums[l] = nums[r];
                    while(l<r&&nums[l]<flag) l++;
                    nums[r] = nums[l];
                }
                nums[l] = flag;
                mySort(nums,left,l);
                mySort(nums,l + 1, right);
            }
        }
    }
    

    那么我们分析如上代码的时间复杂度:
    以上代码的时间复杂度主要存在于mySort函数中:
    在l指针和r指针逐渐向中间靠近的时候,遍历了n个元素,时间复杂度P(n)=cn
    之后递归其左边和其右边的,时间分别为T(k-1)和T(n-k)
    在这里插入图片描述
    将如上公式的展开,得到如下

    在这里插入图片描述
    但是以上公式我勉强看懂了但是记不住,所以贴出以下好理解的方式:

    如果求平均时间复杂度:

    若第一层的话就是n/2,n/2,若是第二层就是n/4,n/4,n/4,n/4这四部分,即n个元素理解上是一共有几层2^x=n,x=logn,然后每层都是n的复杂度,那么平均就是O(nlogn)的时间复杂度。

    展开全文
  • 排序类别,基本思想,排序算法,复杂度分析,稳定性,排序特点分析
  • 时间复杂度与空间复杂度分析

    1、复杂度分析

            复杂度分析是在数据结构和算法我们经常听到的一个概念,因为数据结构和算法解决的是如何更省、更快地存储和处理数据的问题,因此,我们就需要一个考量效率和资源消耗的方法,这就是复杂度分析方法。

    2、时间复杂度

    2.1、只关注循环执行次数最多的一段代码

    因为大О这种复杂度表示方法只是表示一种变化趋势。我们通常会忽略掉公式中的常量、低阶、系数,只需要记录一个最大阶的量级就可以了。所以,我们在分析一个算法、一段代码的时间复杂度的时候,也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的 n 的量级,就是整段要分析代码的时间复杂度。

    2.2、总复杂度等于最高阶的复杂度

    int cal3(int n) {
         int sum_1 = 0;
         for (int p = 1; p < 100; ++p) {
             sum_1 = sum_1 + p;
         }
         int sum_2 = 0;
         for ( int q = 1; q < n; ++q) {
             sum_2 = sum_2 + q;
         }
         int sum_3 = 0;
         for (int i = 1; i <= n; ++i) {
             for (int j = 1; j <= n; ++j) {
                 sum_3 = sum_3 + i * j;
             }
         }
         return sum_1 + sum_2 + sum_3;
     }

            这个代码分为三部分,分别是求sum_1、sum_2、sum_3。我们可以分别分析每一部分的时间复杂度,然后把它们放到一块儿,再取一个量级最大的作为整段代码的复杂度。

            sum_1的时间复杂度是多少呢?这段代码循环执行了100次,所以是一个常量的执行时间,跟n的规模无关。

            注意即便这段代码循环10000次、100000次,只要是一个已知的数,跟n无关,照样也是常量级的执行时间。也就是说不管常量的执行时间多大,我们都可以忽略掉。因为它本身对增长趋势并没有影响。

            那sum_2和sum_3的时间复杂度是多少呢?答案是O(n)和O(n2)。

            那么上面的代码总的时间复杂度是多少?很明显,就是O(n2+n+100)。

            因为n2增长趋势是远快于n的,所以在计算时间复杂度时,我们取其中最大的量级。所以,整段代码的时间复杂度就为O(n2)。也就是说:总的时间复杂度就等于量级最大的那段代码的时间复杂度。那我们将这个规律抽象成公式就是︰

            如果T1(n)=O(fn)),T2(n)=O(g(n));

            那么T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n)))=O(max(f(n), g(n)).

    2.3、嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

    int complexCal(int n) {
            int ret = 0;
            for (int i = 1; i < n; ++i) {
                ret = ret + f(i);
            }
            return ret;
        }
        int f(int n) {
            int sum = 0;
            int i = 1;
            for (; i < n; ++i) {
                sum = sum + i;
            }
            return sum;
        }

            我们单独看complexCal()方法。假设f()只是一个普通的操作,那第4~6行的时间复杂度就是,T1(n)= O(n)。但f()函数本身不是一个简单的操作,它的时间复杂度是T2(n)= O(n),所以,整个cal()函数的时间复杂度就是,T(n)= T1(n)* T2(n)= O(n*n)= O(n2)。

            不过,你并不用刻意去记忆复杂度分析。实际上,复杂度分析这个东西关键在于“熟练”。你只要多看案例,多分析会发现这个分析其实并不难。

    总的来说推导大O阶:

            1.用常数1取代运行时间中的所有加法常数。

            2.在修改后的运行次数函数中,只保留最高阶项。

            3.如果最高阶项存在且不是1,则去除与这个项相乘的常数。得到的结果就是大O阶。

    3、空间复杂度

            时间复杂度的全称是渐进时间复杂度,表示算法的执行时间与数据规模之间的增长关系。同理,空间复杂度全称就是渐进空间复杂度(asymptotic space complexity),表示算法的存储空间与数据规模之间的增长关系。比如:

    void print(int n) {
         int i = 0;
         int[] a = new int[n];
         for (i; i <n; ++i) {
     	    a[i] = i * i;
         }
         for (i = n-1; i >= 0; --i) {
     	    print out a[i]
         }
    }

            在上面的例子中,我们申请了一个空间存储变量i,但是它是常量阶的,跟数据规模n没有关系,所以我们可以忽略。第3行申请了一个大小为n的 int类型数组,除此之外,剩下的代码都没有占用更多的空间,所以整段代码的空间复杂度就是O(n)。

            一般来说,如果算法执行时所需的辅助空间相对于输入数据量而言是个常数,则称此算法为原地工作,空间复杂度为O(1)。

            我们常见的空间复杂度就是O(1)、O(n)、O(n2 ),像O(logn)、O(nlogn)这样的对数阶复杂度平一般很少见,而且,空间复杂度分析比时间复杂度分析要简单很多。所以,我们重点要掌握的还是算法的时间复杂度的问题。

    展开全文
  • 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?为什么需要复杂度分析?大O复杂度表示法;时间复杂度分析;几种常见时间复杂度空间复杂度分析复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度。 ...

    复杂度分析(上):如何分析、统计算法的执行效率和资源消耗


    我们都知道,数据结构和算法本身解决的是“快”和“省”的问题,即如何让代码运行得更快,如何让代码更省存储空间。所以执行效率是算法一个非常重要得考量指标。那如何来衡量编写的算法代码得执行效率呢?这里就要用到**时间、空间复杂度分析**。

    只要讲到数据结构和算法,就一定离不开时间、空间复杂度分析。个人认为,复杂度分析是整个算法学习的精髓,只要掌握了它,数据结构和算法得内容基本上就掌握了一半


    为什么需要复杂度分析?

    初学数据结构和算法,你可能会疑惑,我把代码跑一遍,通过统计、监控,就能得到算法执行时间和占用得内存大小。为什么还要做时间、空间复杂度分析呢?这种分析方法能比我实实在在跑一遍得到的数据更准确吗?

    首先,可以肯定地说,你这种评估算法执行效率得方法是正确的。很多数据结构和算法书籍还给这种方法起了一个名字,叫事后统计法。但是这种方法有非常大的局限性。

    1. 测试结果非常依赖测试环境

    测试环境中硬件的不同会对测试结果有很大的影响。比如,我们拿同样一段代码,分别用Intel Core i9 处理器和Intel Core i3 处理器来运行,不用说,i9 处理器比i3 处理器执行的速度快很多。另外,在不同的机器上两段代码的执行速度可能会有截然相反的结果。

    2. 测试结果受数据规模的影响很大

    对同一个排序算法,待排序数据的有序度不一样,排序的执行时间就会有很大的差别。极端情况下,如果数据已经是有序的,那排序算法不需要做任何操作,执行时间就会非常短。除此之外,如果测试数据规模太小,测试结果可能无法真实地反映算法地性能。比如,对于小规模的数据排序,插入排序可能反倒会比快速排序要快!


    大O复杂度表示法

    算法的执行效率,粗略地讲,就是算法代码执行的时间。但是,如何在不运行代码的情况下,得到一段代码的执行时间呢?

    下面是一段非常简单的代码,求1,2,3…n的累加和。现在,一起来估算一下代码的执行时间。

    int cal(int n){
    	int sum = 0;
    	int i = 1;
    	for(; i <= n; i++){
    		sum += sum + i;
    	}
    	return sum;
    }
    

    从CPU角度来看,这段代码的每一行都执行类似的操作:读数据-运算-写数据。尽管每行代码对应得CPU执行的个数、执行的时间都不一样,但是我们只是粗略估计,所以可以假设每行代码执行的时间是一样的,为unit_time。在这个假设的基础上,这段代码的总执行时间是多少呢?

    第2,3行代码分别需要1个unit_time的执行时间,第4、5行都运行了n遍,所以需要2n * unit_time的执行时间,所以代码的总执行时间就是(2n+2) * unit_time。可以看出,所有代码的执行时间T(n)与每行代码的执行次数成正比。

    尽管我们不知道unit_time的具体值,但是通过上述代码执行时间的推导过程,我们可以得到一个非常重要的规律,所有代码的执行时间T(n)与每行代码的执行次数f(n)成正比

    我们可以把这个规律总结出一个公式。注意,大O要登场了。

    img

    T(n)表示代码执行的时间

    n表示数据规模的大小

    f(n)表示每行代码执行次数的总和

    公式中的O表示代码的执行时间 T(n) 与 f(n)表达式成正比

    大O时间复杂度表示法实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以也叫做渐进时间复杂度。

    当n很大时,公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略。我们只需要记录最大量级即可。


    时间复杂度分析

    如何分析一段代码的时间复杂度?

    1. 只关注循环执行次数最多的一段代码

    大O这种复杂度表示方法只是表示一种变化趋势。我们通常会忽略公式中的常量、低阶、系数,只需要记录一个最大阶的量级就可以了。所以我们在分析一个算法、一段代码的时间复杂度的时候,也只关注循环执行次数最多的那一段代码就可以了。这段核心代码的执行次数的n的量级,就是整段要分析代码的时间复杂度。

    2. 加法法则:总复杂度等于量级最大的那段代码的复杂度

    int cal(int n) {
       int sum_1 = 0;
       int p = 1;
       for (; p < 100; ++p) {
         sum_1 = sum_1 + p;
       }
    
       int sum_2 = 0;
       int q = 1;
       for (; q < n; ++q) {
         sum_2 = sum_2 + q;
       }
     
       int sum_3 = 0;
       int i = 1;
       int j = 1;
       for (; i <= n; ++i) {
         j = 1; 
         for (; j <= n; ++j) {
           sum_3 = sum_3 +  i * j;
         }
       }
     
       return sum_1 + sum_2 + sum_3;
     }
    

    这段代码分成顺序的三部分,分别是求sum_1、sum_2、sum_3。我们可以分析每一部分的时间复杂度,然后把他们放到一块,再取一个量级最大的作为整段代码的复杂度。

    第一段代码循环执行了100次,所以是一个常量的执行时间,与n的规模无关。

    这里要强调一下,即便这段代码循环10000次、100000次,只要是一个已知数,与n无关,照样是常量级的执行时间。当n无限大的时候就可以忽略。尽管对代码执行时间会有很大影响,但是回到时间复杂度的概念来说,它表示的是一个算法执行效率与数据规模增长的变化趋势,所以不管常量的执行时间多大,我们都可用忽略掉,因为它本身对增长趋势并没有影响

    第二段和第三段的时间复杂度分别是O(n)和O(n2),这里就不啰嗦了。

    综合这三段代码的时间复杂度,我们取其中最大的量级。所以,整段代码的时间复杂度就为O(n2)。T1(n)=O(f(n)),T2(n)=O(g(n));那么T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))=O(max(f(n), g(n))))。

    3. 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积


    几种常见时间复杂度

    img img

    对于上述罗列的复杂度量级,我们可以粗略地分为两类,多项式量级和非多项式量级。其中,非多项式量级只有两个:O(2n) 和 O(n!)。

    我们把时间复杂度为非多项式量级的算法问题叫作 NP(Non-Deterministic Polynomial,非确定多项式)问题。

    当数据规模 n 越来越大时,非多项式量级算法的执行时间会急剧增加,求解问题的执行时间会无限增长。所以,非多项式时间复杂度的算法其实是非常低效的算法。因此,关于 NP 时间复杂度我就不展开讲了。我们主要来看几种常见的多项式时间复杂度。

    1. O(1)

    O(1) 只是常量级时间复杂度的一种表示方法,并不是指只执行了一行代码。

    一般情况下,只要算法中不存在循环语句、递归语句,即使有成千上万行的代码,其时间复杂度也是Ο(1),即使有循环语句,但是循环次数固定,那么该段代码的时间复杂度也是O(1)。

    2. O(logn)、O(nlogn)

    对数阶时间复杂度非常常见,同时也是最难分析的一种时间复杂度。通过一个例子来说明一下。

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

    第三行代码是循环执行次数最多的。所以,我们只要能计算出这行代码被执行了多少次,就能知道整段代码的时间复杂度。

    从代码中可以看出,变量 i 的值从 1 开始取,每循环一次就乘以 2。当大于 n 时,循环结束。实际上,变量 i 的取值就是一个等比数列。如果我把它一个一个列出来,就应该是这个样子的:

    img

    所以,我们只要知道 x 值是多少,就知道这行代码执行的次数了。通过 2x=n 求解 x ,得到x=log2(n),所以,这段代码的时间复杂度就是 O(log2n)。

    我们知道,对数之间是可以互相转换的,log3n 就等于 log32 * log2n,所以 O(log3n) = O(C * log2n),其中 C=log32 是一个常量。基于我们前面的一个理论:在采用大 O 标记复杂度的时候,可以忽略系数,即 O(Cf(n)) = O(f(n))。所以,O(log2n) 就等于 O(log3n)。因此,在对数阶时间复杂度的表示方法里,我们忽略对数的“底”,统一表示为 O(logn)。

    如果你理解了我前面讲的 O(logn),那 O(nlogn) 就很容易理解了。还记得我们刚讲的乘法法则吗?如果一段代码的时间复杂度是 O(logn),我们循环执行 n 遍,时间复杂度就是 O(nlogn) 了。而且,O(nlogn) 也是一种非常常见的算法时间复杂度。比如,归并排序、快速排序的时间复杂度都是 O(nlogn)。


    空间复杂度分析

    时间复杂度的全称是渐进时间复杂度,表示算法的执行时间与数据规模之间的增长关系。类比一下,空间复杂度全称就是渐进空间复杂度(asymptotic space complexity),表示算法的存储空间与数据规模之间的增长关系。

    我们常见的空间复杂度就是 O(1)、O(n)、O(n2 ),像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且,空间复杂度分析比时间复杂度分析要简单很多。

    在整段代码中,定义变量的地方是占用空间的地方,值得注意的是数组变量占用的空间是n,后续的操作是对n的内容进行修改,不算占用新的空间。



    复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度

    关于复杂度分析的四个知识点,最好情况时间复杂度最坏情况时间复杂度平均情况时间复杂度均摊时间复杂度。如果能够掌握这几个概念你都能掌握,那么复杂度分析就没什么大问题了。


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

    // n表示数组array的长度
    int find(int[] array, int n, int x) {
      int i = 0;
      int pos = -1;
      for (; i < n; ++i) {
        if (array[i] == x) {
           pos = i;
           break;
        }
      }
      return pos;
    }
    

    这段代码要实现的功能是,在一个无序的数组中,查找变量x出现的位置。如果没有找到就返回-1。

    这段代码的复杂度是O(n)吗?

    当然不是,因为要查找的变量x可能出现在数组的任意位置,如果数组中的第一个元素正好是要查找的变量x,那就不需要继续遍历剩下的n-1个数据了,那时间复杂度就是O(1)。但如果数组中不存在变量x,那我们需要把整个数组都遍历一遍,时间复杂度就成了O(n)。所以,不同情况下,这段代码的时间复杂度是不一样的。

    为了表示代码在不同情况下的不同时间复杂度,我们需要引入三个概念:最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度。

    顾名思义,最好情况时间复杂度就是,在最理想的情况下,执行这段代码的时间复杂度。就像我们刚刚讲到的,在最理想的情况下,要查找的变量 x 正好是数组的第一个元素,这个时候对应的时间复杂度就是最好情况时间复杂度。

    同理,最坏情况时间复杂度就是,在最糟糕的情况下,执行这段代码的时间复杂度。就像刚举的那个例子,如果数组中没有要查找的变量 x,我们需要把整个数组都遍历一遍才行,所以这种最糟糕情况下对应的时间复杂度就是最坏情况时间复杂度。


    平均情况时间复杂度

    最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度,发生的概率其实并不大。为了更好地表示平均情况下的复杂度,我们需要引入另一个概念:平均情况时间复杂度,后面我简称为平均时间复杂度。

    平均时间复杂度又该怎么分析呢?还是借助刚才查找变量 x 的例子来给你解释。要查找的变量 x 在数组中的位置,有 n+1 种情况:在数组的 0~n-1 位置中和不在数组中。我们把每种情况下,查找需要遍历的元素个数累加起来,然后再除以 n+1,就可以得到需要遍历的元素个数的平均值,即:

    img

    我们知道,时间复杂度的大 O 标记法中,可以省略掉系数、低阶、常量,所以,咱们把刚刚这个公式简化之后,得到的平均时间复杂度就是 O(n)。

    这个结论虽然是正确的,但是计算过程稍微有点儿问题。究竟是什么问题呢?我们刚讲的这 n+1 种情况,出现的概率并不是一样的。我们具体分析一下。

    我们知道,要查找的变量 x,要么在数组里,要么就不在数组里。这两种情况对应的概率统计起来很麻烦,为了方便你理解,我们假设在数组中与不在数组中的概率都为 1/2。另外,要查找的数据出现在 0~n-1 这 n 个位置的概率也是一样的,为 1/n。所以,根据概率乘法法则,要查找的数据出现在 0~n-1 中任意位置的概率就是 1/(2n)。

    因此,前面的推导过程中存在的最大问题就是,没有将各种情况发生的概率考虑进去。如果我们把每种情况发生的概率也考虑进去,那平均时间复杂度的计算过程就变成了这样:

    img

    【等差求和公式: n(n+1)/2】

    这个值就是概率论中的加权平均值,也叫作期望值,所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度

    引入概率之后,前面那段代码的加权平均值为 (3n+1)/4。用大 O 表示法来表示,去掉系数和常量,这段代码的加权平均时间复杂度仍然是 O(n)。

    你可能会说,平均时间复杂度分析好复杂啊,还要涉及概率论的知识。实际上,在大多数情况下,我们并不需要区分最好、最坏、平均情况时间复杂度三种情况。像我们前面举的那些例子那样,很多时候,我们使用一个复杂度就可以满足需求了。只有同一块代码在不同的情况下,时间复杂度有量级的差距,我们才会使用这三种复杂度表示法来区分。


    均摊时间复杂度

    到此为止,应该已经掌握了算法复杂度分析的大部分内容了。下面介绍一个更加高级的概念,均摊时间复杂度,以及它对应的分析方法,摊还分析(平摊分析)

    均摊时间复杂度,听起来跟平均时间复杂度分析有点儿像。对于初学者来说,这两个概念确实非常容易混淆。前面说了,大部分情况下,我们并不需要区分最好、最坏、平均三种复杂度。平均复杂度只在某些特殊情况下才会用到,而均摊时间复杂度应用的场景比它更加特殊、更加有限。

    老规矩,还是借助一个具体的例子来帮助你理解。(当然,这个例子只是为了方便讲解想出来的,实际上没人会这么写。)

     // array表示一个长度为n的数组
     // 代码中的array.length就等于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 值放到数组的第一个位置,然后再将新的数据插入。但如果数组一开始就有空闲空间,则直接将数据插入数组。

    那这段代码的时间复杂度是多少呢?可以先用我们刚讲到的三种时间复杂度的分析方法来分析一下。

    最理想的情况下,数组中有空闲空间,我们只需要将数据插入到数组下标为 count 的位置就可以了,所以最好情况时间复杂度为 O(1)。最坏的情况下,数组中没有空闲空间了,我们需要先做一次数组的遍历求和,然后再将数据插入,所以最坏情况时间复杂度为 O(n)。

    那平均时间复杂度是多少呢?答案是 O(1)。我们还是可以通过前面讲的概率论的方法来分析。假设数组的长度是 n,根据数据插入的位置的不同,我们可以分为 n 种情况,每种情况的时间复杂度是O(1)。除此之外,还有一种“额外”的情况,就是在数组没有空闲空间时插入一个数据,这个时候的时间复杂度是 O(n)。而且,这 n+1 种情况发生的概率一样,都是 1/(n+1)。所以,根据加权平均的计算方法,我们求得的平均时间复杂度就是:

    img

    至此为止,前面的最好、最坏、平均时间复杂度的计算,理解起来应该都没有问题。但是这个例子里的平均复杂度分析其实并不需要这么复杂,不需要引入概率论的知识。这是为什么呢?

    我们先来对比一下这个 insert() 的例子和前面那个 find() 的例子,你就会发现这两者有很大差别

    首先,find()函数是按值查找,它是要一个一个遍历查找的,只有在极端情况下,复杂度才为 O(1)。但 insert() 在大部分情况下,时间复杂度都为 O(1),只有个别情况下,复杂度才比较高,才为 O(n)。这是 insert()第一个区别于 find() 的地方。

    我们再来看第二个不同的地方。对于 insert() 函数来说,O(1) 时间复杂度的插入和 O(n) 时间复杂度的插入,出现的频率是非常有规律的,而且有一定的前后时序关系,一般都是一个 O(n) 插入之后,紧跟着 n-1 个 O(1) 的插入操作,循环往复。

    所以,针对这样一种特殊场景的复杂度分析,我们并不需要像之前讲平均复杂度分析方法那样,找出所有的输入情况及相应的发生概率,然后再计算加权平均值。

    针对这种特殊的场景,我们引入了一种更加简单的分析方法:摊还分析法,通过摊还分析得到的时间复杂度我们起了一个名字,叫均摊时间复杂度

    如何使用摊还分析法来分析算法的均摊时间复杂度呢?

    我们还是继续看在数组中插入数据的这个例子。每1次 O(n) 的插入操作,都会跟着 n-1 次 O(1) 的插入操作,所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上,均摊下来,这一组连续的操作的均摊时间复杂度就是 O(1)。这就是均摊分析的大致思路。

    本质: (n+n-1)/n=2 ——> O(1)

    n次包含1次O(n)的插入操作和 n-1次O(1)的插入操作

    均摊时间复杂度和摊还分析应用场景比较特殊,所以我们并不会经常用到。为了方便理解、记忆,我这里简单总结一下它们的应用场景

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

    在能够应用均摊时间复杂度分析的场合,均摊结果一般都等于低级别复杂度,一般均摊时间复杂度就等于最好情况时间复杂度。

    平均时间复杂度存在随机性,均摊时间复杂度则是具有规律性,但两者都存在概率的问题,我个人认为,均摊时间复杂度就是一种特殊的平均时间复杂度,我们没必要花太多精力去区分它们。你最应该掌握的是它的分析方法,摊还分析。至于分析出来的结果是叫平均还是叫均摊,这只是个说法,并不重要。

    展开全文
  • 基于Python和Coh-Metrix高考英语“一年两考”阅读文本复杂度分析
  • 各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。
  • 空间复杂度分析

    2022-04-15 08:57:25
    空间复杂度分析1.空间复杂度定义 1.空间复杂度定义 是对一个算法在运行过程中占用内存空间大小的量度,记做S(n)=O(f(n))S(n)=O(f(n))S(n)=O(f(n))。 空间复杂度(Space Complexity)记作S(n)S(n)S(n)依然使用大OOO来...
  • 矩阵求逆操作的复杂度分析 逆矩阵的复杂度分析 1 背景 之前写过一篇关于矩阵复杂度分析的文章,没有想到阅读人数那么多。对于IT相关人士来说,从代码层次再结合基本数学知识,就能够很好地理解矩阵的复杂度如何计算...
  • 复杂度分析(二)

    2020-12-05 17:11:31
    文章目录复杂度分析(二)01、最好、最坏情况时间复杂度02、平均情况时间复杂度03、均摊时间复杂度 复杂度分析(二) 01、最好、最坏情况时间复杂度 // n 表示数组 array 的长度 int find(int[] array, int n, int x...
  • 格困难问题的复杂度分析 作为新型的密码系统, 格密码因为其巨大的潜在应用价值备受关注. 作为格密码的基石, 格困 难问题一直是格密码研究的重点. 本文通过分析一些常见的格问题, 主要包括最短向量问题(SVP), 最近 ...
  • 这个主要介绍了匹配追踪算法,同时有着对匹配追踪复杂度分析
  • DQN算法的时间复杂度分析

    千次阅读 多人点赞 2021-05-21 06:43:44
    时间复杂度: 设: Initialize replay memory D\mathcal{D}D to capacity NNN (运行消耗t0t_0t0​时间) Initialize action-value function QQQ with random weights (运行消耗t1t_1t1​时间) for episode=1,...
  • 目录 一、快排时间复杂度分析 二、归并排序时间复杂度分析 三、写在最后 一、快排时间复杂度分析 快速排序的时间复杂度在O(nlogn)~ O(n^2)之间,下面我分别分析这两种情况: (一)快速排序的最好情况O(nlogn) ...
  • 算法时空复杂度分析

    千次阅读 2020-09-01 20:29:55
    文章目录算法时空复杂度分析0.为什么要学习算法时空复杂度分析1.理论2.分析方法3.大O复杂度表示法4.多项式量级复杂度5.时间复杂度分析的简单规则6.两种时间复杂度7.常见的时间复杂度8.空间复杂度分析9.不同情况下的...
  • 复杂度分析 一、分类 分为时间复杂度和空间复杂度 写在前面: 数据规模:个人理解:指运行该代码块运算出的数据的数量级 如果要想在1s之内解决问题: O(n^2)的算法可以处理大约10^4级别的数据 O(n)的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 443,635
精华内容 177,454
关键字:

复杂度分析

友情链接: 串口小助手.rar