算法的分析

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

• 代价： 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

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