IT培训-高端面授IT培训机构
云和教育:云和数据集团高端IT职业教育品牌 全国咨询热线:0371-67988003
课程 请选择课程
    校区 请选择校区
      • 华为
        授权培训中心
      • 腾讯云
        一级认证培训中心
      • 百度营销大学
        豫陕深授权运营中心
      • Oracle甲骨文
        OAEP中心
      • Microsoft Azure
        微软云合作伙伴
      • Unity公司
        战略合作伙伴
      • 普华基础软件
        战略合作伙伴
      • 新开普(股票代码300248)
        旗下丹诚开普投资
      • 中国互联网百强企业锐之旗
        旗下锐旗资本投资

      怎样进行算法的复杂度分析?

      • 发布时间:
        2023-03-09
      • 版权所有:
        云和教育
      • 分享:

       

      复杂度分析是估算算法执行效率的方法,公式O(f(n))表示算法的复杂度,此方法即为大O复杂度表示法O(f(n))中n表示数据规模,f(n)表示运行算法所需要执行的指令数。

      大O复杂度表示法

      下面的代码非常简单,求 1,2,3…n 的累加和,我们要做的是估算它的执行效率。

      def calc(n):
          sum_ = 0
          for i in range(1,n+1):
              sum_ = sum_ + i
          return sum_

      假设每行代码执行的时间都一样为t,执行第2行代码需要时间t,第3,4行代码运行了n遍,需要的时间为2n*t,这段代码总执行时间为(2n+1)* t

      结论:代码执行的总时间T(n)与每行代码的执行次数成正比

      看下面的代码,估算该段代码的执行时间:

      def calc(n):
          sum_ = 0
          for i in range(n):
              for j in range(n):
                  sum_ = sum_ + i*j
          return sum_

      同样假设每行代码执行的时间都一样为t:执行第2行代码需要时间t,第3行代码运行了n遍,需要时间为n*t,第4、5行代码运行了n2次,需要时间为2n2 * t,执行所有代码的总时间为 (2n2 + n + 1)* t。

      结论:代码执行的总时间T(n)与每行代码的执行次数成正比。

      用O(f(n))来表示算法复杂度:

      def calc(n):
          sum_ = 0
          for i in range(1,n+1):
              sum_ = sum_ + i
          return sum_
      def calc(n):
          sum_ = 0
          for i in range(n):
              for j in range(n):
                  sum_ = sum_ + i*j
          return sum_

      T(n) = O(f(n)) , O表示代码的执行时间T(n) 与 f(n)表达式成比例。

      大O复杂度表示法:上面例子中的T(n) = O(2n+1), 另一个 T(n) = O(2n² + n + 1)。大O时间复杂度并不表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

      当数据量特别大, 也就是n的取值很大的时候,大O表示法中低阶、常量、系数三部分并不会左右增长趋势,可以忽略。

      def calc(n):
          sum_ = 0
          for i in range(1,n+1):
              sum_ = sum_ + i
          return sum_
      def calc(n):
          sum_ = 0
          for i in range(n):
              for j in range(n):
                  sum_ = sum_ + i*j
          return sum_

      上面例子中的T(n) = O(2n+1), 另一个 T(n) = O(2n² + n + 1),用大O表示法表示上面两段代码的时间复杂度,可以记为O(n),O(n²)。

      算法A: O(n) 执行指令,10000*n

      def calc(n):
          sum_ = 0
          for i in range(1,n+1):
              sum_ = sum_ + I
        """
        此处省略n行... ...
        """
          return sum_

      算法B: O(n²) 执行指令数,10*n2

      对比上面两个算法,当 n = 10, n=100 时, 算法B执行的速度更快,n = 1000 时两者速度相当

      n = 104 , n = 105, n = 106 ,算法A执行的速度更快的

      随着数据规模的进一步增大, 这个差距会越来越大

      时间复杂度分析

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

      在分析一个算法、一段代码的时间复杂度时,只关注循环执行次数最多的那一段代码就可以了。

      def calc(n):
          sum_ = 0
          for i in range(n):
              for j in range(n):
                  sum_ = sum_ + i*j
          return sum_

      上面的代码中,我们只需要关注内层for循环的时间复杂度就可以了,内层for循环的两行代码被执行了n2次,所以总的时间复杂度就是O(n²)

      总复杂度等于量级最大的那段代码的复杂度

      def calc(n):
      sum_ = 0
          for i in range(1,n+1):
              sum_ = sum_ + i
          sum_1 = 0
          for i in range(1,n+1):
              for j in range(n):
                  sum_1 = sum_1 + i*j
          return sum_+sum_1

      上面的代码分为两部分,分别是求 sum_、sum_1,计算sum_部分的代码段时间复杂度O(n),计算sum_1部分的代码段时间复杂度为O(n²) ,总的时间复杂度由复杂度最大的部分决定, 所以上面代码复杂度为O(n²)。

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

      def fn(n):
          sum_ = 0
          for i in range(n+1):
              sum_ = sum_ + i
          return sum_
      def calc(n):
          sum_ = 0
          for i in range(n+1):
              sum_ = sum_ + fn(i)
          return sum_

      上面的代码中第二个函数调用了第一个函数, 如果把fn函数调用当作一个普通操作, 那么第二个函数的时间复杂度为O(n) Fn函数的时间复杂度为O(n),那么函数整体的时间复杂度为O(n*n) = O(n²)。

      当两段代码的数据规模不同时,不能省略复杂度低的部分

      def calc(n):
      sum_ = 0
          for i in range(1,n+1):
              sum_ = sum_ + i
          sum_1 = 0
          for i in range(1,m+1):
              for j in range(m):
                  sum_1 = sum_1 + i*j
          return sum_+sum_1

      上面的代码分为两部分,分别是求 sum_、sum_1,计算sum_部分的代码段时间复杂度O(n),计算sum_1部分的代码段时间复杂度为O(m2) ,总的时间复杂度由复杂度最大的部分决定, 所以上面代码复杂度为O(m²+n)