循环不等式：用于帮助验证算法的正确性，共有三个性质
1初始化：在循环的第一轮迭代开始前，是正确的
2保持：在循环的某一次迭代开始前是正确的，在下一次迭代前，也该正确
3终止：循环结束时，不等式给了我们一个有用的性质，有助于表明算法是正确的
算法步骤：反应出运行时间，主要占用运行时间的是各个循环，递归，其重复次数多，对于单次循环时间可令为常数c，c*n则为具体运行时间
（一）插入排序法：部分排好序--单个数插入，类似迭代（属于增量法：在排好的数组中插入，形成新数组）
插入排序法
算法的步骤为n^2，两个内嵌的for循环
（二）合并排序法：（属于分治法：类似递归）在每个递归，可分为三个步骤
1分解：将原问题分解为一系列子问题
2解决：递归的解各个子问题，若子问题够小，可直接求解
3合并：将子问题的解合并成原问题的解
合并排序法
算法步骤为nlgn:n表示数据的个数，lgn表示该数据的层数，是为2为底的对数，即递归次数
（三）冒泡法：重复交换相邻的两个反序元素
算法步骤：1+2+3.+.......n,所以数量级为n^2
案例：逆序对，若i<j时，A[i]>A[j],则（i,j）为A中的一个逆序对
子函数，求解两个有序数组间的逆序对
通过递归将一个数组不断细分，再合并
总结：通过循环不等式可判断算法是否有错，通过计算算法的运行时间可判断该算法的效率
将求解逆序对的过程转化成排序问题，降低算法步骤
网友评论