算法导论-算法入门学习笔记．

插入排序：

输入： n 个数

输出： n个数的一个排列，使得它们之间有序。

INSERTION_SORT(A)

    for j <-- 2 to length[A]

        do key <-- A[j]

           i = j - 1

           while i > 0 and A[i] > key /* 降序只需要改变比较条件即可 */

                do  A[i+1] = A[i] 

                    i = i - 1 

            A[i+1] = key

            

            

算法分析：

    指对一个算法所需要的资源进行预测。内存，通信带宽或计算机硬件等资源偶尔是我们主要关心的。

    但通常，资源是指我们希望测度的计算时间。也就是说，对于一个给定的问题，通过分析几种候选算法，

    从中选出一个最有效的算法。

    

    分析算法之前，首先要建立有关实现技术的模型，包括描述所用资源以及代价的模型。（单处理机，RAM 计算模型 ) 

    算法的运行时间是指在特定输入时，所执行的基本操作数（步数）。

    

假设；

    每执行一行代码都要花一定量的时间，虽然每一行所花的时间有所不同，但我们假定每次执行第ｉ行所花的时间都是常量Ｃi.

    cost: 第ｉ行执行所花的时间Ci.

    times: 第i行执行次数.

    tj 为while 循环所做的测试次数.测试要比循环体多一次.

    

    INSERTION_SORT(A)                           cost            times

    for j <-- 2 to length[A]                    c1              n

        do key <-- A[j]                         c2              n-1

           i = j - 1                            c3              n-1

           while i > 0 and A[i] > key           c4              Tj (j =2--->n 之和)

                do  A[i+1] = A[i]               c5              (tj-1)

                    i = i - 1                   c6              (tj-1)

            A[i+1] = key                        c7              n-1

            

            T[n] = 每一对cost 与 times 的积求和.

            

           

            

结论：

    一个算法运行时间对于某一给定输入来说，往往是固定的。同时

    

最坏情况和平均情况分析：

    最坏情况运行时间:

        对于规模为ｎ的任何输入，算法的最长运行时间。

             1.一个算法在最坏情况运行时间是在任何输入下运行时间的一个上界.

             2.对某些算法来说，最坏情况出现的相当频繁.

             3.　大致上看，平均情况和最坏情况一样差.

            

形式化说明：　插入排序的问题，就是在选定key为A[j]时，决定应该在子数组A[1..j-1] 中的哪一个位置上插入A[j] .   

某些情况下，可能对一个算法的平均运行情况或期望运行时间感兴趣，可通过概率分析技术来确定。但同时也存在一个问题，

就是对某个特定的问题来说，平均输入是由那些东西构成的可能不一定很明显。因此假定某一规模的所有输入都是等可能的。

算法分析，是对计算过程进行简化抽象，考虑不同问题输入规模时从时空复杂度来决定解决该问题应该选取什么算法。