算法运行时间分析方法

      我们对算法进行分析，主要考察算法效率和占用资源空间。而算法效率的考察我们这里用最坏情况运行时间去衡量……
    通过对《算法导论》的学习，一般分析算法效率的方法无外直接分析法和递归式。一下我们将分别举例说明.
      1.  直接分析法：就是对算法本身进行直接分析，推理出运行时间。我们这里以插入算法为例：
      插入算法代码

//直接插入排序
void straightInsertSort(int *a,int n)
{
    int i,j;
    int temp;
    //逐个记录插入有序序列
    for(i=2;i<=n;i++){
        temp=a[i];
        //把a[i]插入有序序列
        for(j=i-1;j>=1;j--){
            if(temp<a[j]){
                a[j+1]=a[j];
            }else
                break;
        }
        a[j+1]=temp;
    }
}

 

从上面代码容易看出，要插入的记录个数为n-1，其中关键字的比较次数和记录移动次数是依赖于给出的待排序序列是否基本有序。在最佳情况下（待排序序列有序），比较次数和移动次数时间为o（1），所以时间复杂度为o（n）.在最坏情况下（待排序序列逆序）和平均时间均为o（n^2）.从上述分析中可以看出，直接插入排序适合记录数比较少、给定序列基本有序的情况。熟悉了排序过程我们发现，直接插入排序是一种稳定的原地排序算法。
    2.  递推式：就是对算法进行直接分析，得出递推式，然后求解递推式。
        一般有如T(n)=aT(n/b)+f(n)的表达，对于这种递推式介绍三种求解递推方法。
       代入法；我们猜测一个界，然后用数学归纳法证明这个界是正确的。
       递归树法：将递归式转换为一颗树，其结点表示不同层次的递归调用产生的代码。然后采用边界和技术求解。

　　在引入递归树之前可以考虑一个例子：

　　T(n) = 2T(n/2) + n²

　　迭代2次可以得：

　　T(n) = n² + 2(2T(n/4) + (n/2) ²)

　　还可以继续迭代，将其完全展开可得：

　　T(n) = n² + 2((n/2) ² + 2((n/2²)² + 2((n/2³) ² + 2((n/2⁴) ² +…+2((n/2ⁱ) ² + 2T(n/2^{i + 1})))…))))　　……(1)

　　而当n/2ⁱ⁺¹ == 1时，迭代结束。

 

　　将(1)式小括号展开，可得：

　　T(n) = n² + 2(n/2)² + 2²(n/2²) ² + … + 2ⁱ(n/2ⁱ)² + 2ⁱ⁺¹T(n/2ⁱ⁺¹)

　　这恰好是一个树形结构，由此可引出递归树法。

 

　　图中的(a)(b)(c)(d)分别是递归树生成的第1,2,3,n步。每一节点中都将当前的自由项n²留在其中，而将两个递归项T(n/2) + T(n/2)分别摊给了他的两个子节点，如此循环。

　　图中所有节点之和为:

　　[1 + 1/2 + (1/2)² + (1/2)³ + … + (1/2)ⁱ] n² = 2n²

　　可知其时间复杂度为O(n²)

　　

　　可以得到递归树的规则为：

　　(1) 每层的节点为T(n) = kT(n / m) + f(n)中的f(n)在当前的n/m下的值；

　　(2) 每个节点的分支数为k；

　　(3)每层的右侧标出当前层中所有节点的和。

 

　　再举个例子：

　　T(n) = T(n/3) + T(2n/3) + n

　　其递归树如下图所示：

　　

　　可见每层的值都为n，从根到叶节点的最长路径是：

　　

　　因为最后递归的停止是在(2/3)^kn == 1.则

　　　　　　

　　于是

　　　　

　　即T(n) = O(nlogn)　

       主方法：

　　对于一个递归实现的分治算法，其时间复杂度表示为：

　　T(n) = aT(n/b)+h(n)

　　其中，a>=1; b>1; h(n)是不参与递归部分的时间复杂度。

　　比较n^log b (a)与Θ(h(n)) 的大小(Θ的含义和“等于”类似，而大O的含义和“小于等于”类似，感觉好像这里都可以用)：

　　若n^log b (a)= Θ(h(n)) ：该方法的复杂度为 Θ(h(n)*log(n))

　　若n^log b (a)< Θ(h(n)) ：该方法的复杂度为 Θ(h(n))

　　若n^log b (a)> Θ(h(n)) ：该方法的复杂度为 Θ(n^log b (a))

　　例如：

　　T(n) = T(n/2)+1：Θ(log(n))(二分查找)

　　T(n) = 2T(n/2)+n ：Θ(n*log(n))(归并排序)

　　以上都属于“等于”的情况。