美文网首页学习笔记
算法导论第2.2章 - 算法的分析

算法导论第2.2章 - 算法的分析

作者: 彩虹小星星 | 来源:发表于2021-09-08 11:18 被阅读0次

    算法的分析

    定义:通常来说我们想要度量算法的运行时间
    表达方式:把运行时间描述成一个输入规模的函数
    输入规模可以是待排序的数组的规模,输入元素的数量等
    具体算法:针对每行代码,计算出代价和次数,并加权求总

    • 代价: ci代表第i行代码执行所需要的时间。(它是一个常量)
    • 次数: 执行/循环的次数 (当一个for 或者 while循环按正常方式退出时,执行测试的次数比执行循环体的次数多1)
      次数是一个关于输入规模n的函数,
      通常我们考虑最坏的情况和平均情况的分析。

    增长量级
    专注于最坏情况下的n的最高阶
    *因为当n足够大的时候,常量c和低阶n的影响没有那么大。

    练习

    2.2-1

    Θ(n^3)

    2.2-2

    MY-SWAP(A)
      for i = 1 to A.length - 1
          min = i
          for j = i+1 to A.length
              if A[j] < A[min]
                min = j
          minA = A[j]
          A[j] = A[i]
          A[i] = minA
      return A
    

    2.2-3

    MY-ADD(A, B)
      C[1] = 0                                       //  平均和最差情况都是1步
      for i = 1 to n                                 //  平均情况:(1+2+...+n)/n = (1+n)/2  ; 最差情况:n
        C[i] = (A[i] + B[i] + C[i]) % 2              //  同上
        C[i+1] = (A[i] + B[i] + C[i]) / 2            //  同上
      return C                                       //  平均和最差情况都是1步
    

    平均情况下: T(n) = (1+n)/2 + 2 = n/2 + 2.5 也就是说 Θ(n)
    最差情况下: T(n) = n*3 + 2 也就是说 Θ(n)

    2.2-4

    让算法的增长量级尽量控制在低阶的情况下

    相关文章

      网友评论

        本文标题:算法导论第2.2章 - 算法的分析

        本文链接:https://www.haomeiwen.com/subject/ufcmwltx.html