算法的效率的分析：

• 就是指算法求解一个问题所需要的时间和空间
• 时间资源和空间资源
• 计算模型
  • Turing机以及RAM等

• 算法时间资源的估算

  • 算法执行基本运算的数目

    度量一个算法运行时间的三种方式：

• 最好情形时间复杂度

• 最坏情形时间复杂度
• 平局情形时间复杂度

  插入排序算法复杂度分析：

  插入排序算法的每一步的执行次数

  

  算法的总计算次数

  

  最好的情况

  即输入的序列原本就是有序的序列，在这种情况下，不需要在进行排序，只相当于遍历整个序列去验证一下是否是有序的，所以每次都不会进入while循环，所以他们都不执行
  

  最坏的情况

  最差的情况就是输入的序列为一个逆序的序列
  
  1，当初始序列为正序时，只需要外循环n-1次，每次进行一次比较，无需移动元素。此时比较次数（）和移动次数（）达到最小值。
  =n-1，即只需要进行n-1次外层循环
  =0，内存循环不需要，因为不需要移动数据
  此时时间复杂度为。
  2，当初始序列为反序时，需要外循环n-1次，每次排序中待插入的元素都要和[0,i-1]中的i个元素进行比较且要将这i个元素后移i次，加上tmp=arr[i]与arr[j]=temp的两次移动，每趟移动次数为i+2,此时比较次数和移动次数达到最大值。
  = 1+2+…+(n-1) = n(n-1)/2=
  = （1+2）+ （2+2）+…..+（n-1+2）=（n-1）(n+4)/2=
  此时时间复杂度
  3，在直接插入排序中只使用了i,j,tmp这三个辅助元素，与问题规模无关，空间复杂度为。
  4，相同元素的相对位置不变，如果两个元素相同，插入元素放在相同元素后面。是一种稳定排序