Felomeng算法导论(第二版)学习笔记Chapter2(使用C#实现)

时间:2022-01-11 10:19:18

第二章       Getting Started

插入排序(Insertion SortC#实现:

            int i,j,key;

            for( j = 1; j < numbers.Length; j ++)

            {

                key = Convert.ToInt32(numbers[j]);

                i = j - 1;

                while (i >= 0 && Convert.ToInt32(numbers[i]) > key)

                {

                    numbers[i + 1] = numbers[i];

                    --i;

                 }

                numbers[i + 1] = key.ToString();

            }

循环不变性(Loop invariant)三要素:

初始化:第一次循环前“有序性”是成立的;

保持:“有序性”,如果在一次循环前为真,那么在下次循环前仍然为真

结束:当循环结束时,“有序性”仍然成立,从而证明算法是正确的。

Felomeng算法导论(第二版)学习笔记Chapter2(使用C#实现)

上面时间复杂度最坏情况为T(n)= θ(n*n)

平均情况(average-case)和最坏情况(worst-case

一般采取最坏情况,原因: 

1.         最坏情况的运行时间(running time)是程序可能的最长时间,不会与人们的预期冲突(只会小于预期)。

2.         最坏情况在很多情况下经常出现。

3.         平均情况往往和最坏情况差不多糟糕。

合并排序算法(merge sort),使用各个击破方法(divide-and-conquer approach

主过程:

            int[] A = new int[numbers.Length];

            for (int i = 0; i < numbers.Length; i++)

            {

                A[i] = Convert.ToInt32(numbers[i]);

            }

            A = Merge(A, 0, A.Length - 1);

合并算法:

        private int[] Merge(int[] A,int p, int q, int r)

        {

            int n1, n2;

            n1 = q - p + 1;

            n2 = r - q;

            int[] L = new int[n1 + 1];

            int[] R = new int[n2 + 1];

            int i, j;

            for (i = 0; i < n1; i++)

            {

                L[i] = A[i + p];

            }

            for (j = 0; j < n2; j++)

            {

                R[j] = A[j + q + 1];

            }

            L[n1] = int.MaxValue;

            R[n2] = int.MaxValue;

            i = 0;

            j = 0;

            for (int k = p; k <= r; k++)

            {

                if (L[i] <= R[j])

                {

                    A[k] = L[i];

                    i++;

                }

                else

                {

                    A[k] = R[j];

                    j++;

                }

            }

            return A;

        }

 

        private int[] Merge(int[] A,int p, int r)

        {

            int q = 0;

            if (p < r)

            {

                q = (p + r) / 2;

                A = Merge(A, p, q);

                A = Merge(A, q + 1, r);

                A = Merge(A, p, q, r);

            }

            return A;

        }

合并排序算法分析:

Felomeng算法导论(第二版)学习笔记Chapter2(使用C#实现)

 

可以看到,每一步消耗掉的时间都是cn。为什么呢?因为每步都有 方个运算,每个运算中消耗的时间是cn/(2^i ),这是因为每个运算中只有n/(2^i)个数进行排序,而排序需要的时间和排序的数字数线性相关。所以最后每步消耗时间c * n/(2^i)cn

总共进行了lgn次运算,lgn表示底数为2n的对数。假设总共进行了i+1(第一步是 )步运算,最后一步n/ (2^i)=1,所以i = lgn

于是根据乘法原理(高中数学),最后总共用时(lgn+1)*cn=cn*lgn +cn,因为cn远比cn*lgn增长率小,所以时间复杂度T(n)=θ(n*lgn)

 

 

为了说明这个算法的时间复杂度,书中给了限定条件:假设要解决的问题的数字数是2的乘方倍,其实不加这些条件限制,最后的结论也是一样的。(书里说后面章节会介绍清楚)