《算法导论》第一讲

简介: 版权声明:您好,转载请留下本人博客的地址,谢谢 https://blog.csdn.net/hongbochen1223/article/details/47667691 首先讲的就是排序问题,也就是在算法中的经典问题,在这一讲中主要讲了两个排序问题,一个是插入排序,一个是归并排序,在这里,并不是将如何去实现这个排序,而是通过这两个排序来学习渐进分析的原理以及其对应的符号。
版权声明:您好,转载请留下本人博客的地址,谢谢 https://blog.csdn.net/hongbochen1223/article/details/47667691

首先讲的就是排序问题,也就是在算法中的经典问题,在这一讲中主要讲了两个排序问题,一个是插入排序,一个是归并排序,在这里,并不是将如何去实现这个排序,而是通过这两个排序来学习渐进分析的原理以及其对应的符号。

1:排序问题

对于一个序列

InsertionSort(A,n) //对A[1,2,...n]进行排序
    for j<-2 to n
        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

在使用伪代码的时候,我们不使用括号进行分界,而是使用缩进进行分界。

首先我们看一下整体的排序流程:

这里写图片描述

在排序的过程中是有一个常量的,在排序过程中保持不变,也就是前后的顺序是不变的,因为key前面的元素的前后顺序已经确定了。

我们来举个例子看一下:

8 2 4 9 3 6    //首先,我们从j=2开始,2 < 8,也就是8 > 2,所以2和8为位置调换

2 8 4 9 3 6    //接着,key = 4,8 > 4,2 < 4,所以8和4的位置调换

2 4 8 9 3 6    //接着,key = 9,8 < 9,所以位置不变

2 4 8 9 3 6    //接着,key = 3,9 > 3,9和3的位置调换,8 > 3,8和3的位置调换,4 > 3,4和3的位置调换,2 < 3,所以位置不变

2 3 4 8 9 6    //接着,key = 6,9 > 6,9和6的位置调换,8 > 6,8和6的位置调换,4 < 6,位置不变,

2 3 4 6 8 9    //这样排序就完成了。

下面我们使用工具来分析一下这个排序算法:

1:运行时间问题

对于程序的运行时间,取决于很多因素
1:取决于输入的顺序,最坏的情况下就是逆序
2:取决于输入数据的数量大小
我们在进行分析的时候,是将输入的规模参数化。

2:运行时间的上界

在我们进行算法分析的时候,经常对算法的运行时间的上界感兴趣,因为这对程序的效率比较时非常有效的,如果是运行时间下界的话,我们可能不知道该程序的最长运行时间是多少,有可能是很长很长的时间,都不好说,所以,对于一个算法的运行时间上界的分析,是非常有用的。

这里的运行时间的上界其实就是在最坏情况下程序的运行时间,在这里我们刚刚说了,当输入为逆序的时候,就是最坏情况。我们就来分析一下。

我们使用T(n)代表n个输入数据的最长运行时间。

而我们又知道,程序的运行时间和计算机的配置也是有关系的,在这里我们使用的是对相同机器上的表现。

在这里我们使用渐进分析程序的运行时间的上界。

渐进分析的意思就是忽略掉那些依赖于机器的常量,不去检查实际的运行时间,而是关注运行时间的增长。在我们进行渐进分析的时候,需要使用一些符号来理解渐进分析。
第一个需要了解的就是θ符号。

θ:写一个公式,舍弃他的低阶项,并忽略掉前面的常数因子

举个例子:

这里写图片描述

当n->无穷的时候,θ(n2)的程序总会战胜一个θ(n3)的程序,我们来看一下下面这张图片,就能印证这段话。

这里写图片描述

对于我们这个插入排血来说,我们使用内存引用计数来计算一下该算法的最坏情况下的运行时间。

这里写图片描述

在这里我们可以看出,当n比较小的时候,该算法的运行时间还是可以的,但是当n非常大的时候,该算法的运行时间是相当缓慢的。

下面我们来介绍一个更快的排序算法,叫做归并排序。

(二):归并排序

归并排序的思想就是分而治之的思想,将已有顺序的子序列进行合并,得到完全有序的序列。

在我们对A[1,2,3…N]进行归并排序的时候,通常需要三步:

1:如果n = 1,排序完成
2:递归的对A[1 到 n/2向上取整]这部分和A[n/2+1向上取整 到 n]分成两半
3:拍好顺序之后对两个表进行归并

下面我们举个例子,下面是已经排好序的两张表,我们来看一下如何归并。

20    12
13    11    
7      9    
2      1

两个表是竖着的。

首先比较的是1和2,其中1最小,将1输出。
1
接着,比较2和9,2最小,将2输出
1 2
接着,比较9和7,7最小,将7输出
1 2 7
再比较9和13,9最小,将9输出
1 2 7 9
再比较13和11,11最小,将11输出
1 2 7 9 11
在比较13和12,12最小,将12输出
1 2 7 9 11 12
最后只剩下一个表了,将表中的数据按顺序输出
1 2 7 9 11 12 13 20

这样,通过归并,我们就将顺序排出来了。

下面我们来分析一下这个算法。

我们通过上面的三个步骤进行分析。其中1,2,3分别代表上面的三个步骤。

1 : 第一个步骤,我们是直接进行判断 n 是否等于1,如果等于1的话,直接输出,所以这里的T(n)是一个常数,我们使用θ(1)来表示
2:第二个步骤,我们对序列进行递归分成两半,这里的时间 = 2T(n/2)
3:第三个步骤,进行归并,我们需要比较n次,所以,这里的T = θ(n)

通过这三个步骤,我们总结出一个方程:

这里写图片描述

下面为了容易分析,我们将公式总结成下面这个公式:

这里写图片描述

其中,使用cn代替θ(n)

对于递归程序,我们使用递归树的方法进行分析。

这里写图片描述

好了,根据上面的递归图,我们总结一下:

1:树的高度:lgn
2:叶子的个数:n
3:总和:cn * lgn + θ(n) = cn * lgn = θ(nlgn)
注意在求总和的时候,我们可以这样看,每一行的和都是cn,那么总和就是cn乘上数的高度,这样就得来了这个算法的复杂度 θ(nlgn)

很明显,在大规模的情况下,归并算法要优于插入排序。

目录
相关文章
|
5月前
|
存储 算法 搜索推荐
算法导论
算法导论
算法导论(第三版)具体算法解析与理解
算法导论(第三版)具体算法解析与理解
|
算法 Java 索引
数据结构与算法之美 | 别怕,有我!KMP 算法详解
为什么我认为 KMP 算法就是个动态规划问题呢,等会再解释。对于动态规划,之前多次强调了要明确 dp 数组的含义,而且同一个问题可能有不止一种定义 dp 数组含义的方法,不同的定义会有不同的解法。
数据结构与算法之美 | 别怕,有我!KMP 算法详解
|
算法
数据结构与算法之八皇后问题
八皇后问题代码实现 package com.pionner.recursion; public class Queen8 { int max = 8; int[] array = new int[max]; static int i = 0; public...
790 0
|
算法
算法导论——贪心算法
贪心算法(greedy algorithm)是指,在每一步都做出当时看起来最佳的选择,也就是局部最优的选择,期望这样的选择能够导向全局最优解。所以并不是所有的问题都能得到全局最优解。          典型的例子如分数背包问题:背包容量为50kg,有三个商品分别是重60元/10kg、100元/20kg、120元/30kg,商品可以分割,如何选取商品使背包价值最大。
1501 0
|
移动开发 算法 BI
算法导论——动态规划
  动态规划指的是一个问题可以拆分成多个小的最优子问题,并且这些子问题具有重叠,典型的如斐波那契数列:f(2)=f(1)+f(0),f(3)=f(2)+f(1),f(4)=f(3)+f(2),若使用简单的递归算法求f(4),则f(2)会被计算两次,当计算f(n)时需要计算f(n-1)和f(n-2)而f(n-1)又要计算记一次f(n-2),如此往复时间复杂度为n的指数级别,导致算法效率低下。
1456 0
|
算法 Python 机器学习/深度学习
|
算法
《算法导论(原书第3版)》一导读
本书的设计目标是全面、适用于多种用途。它可用于若干课程,从本科生的数据结构课程到研究生的算法课程。由于书中给出的内容比较多,只讲一学期一般讲不完,因此,教师们应该将本书看成是一种“缓存区”或“瑞典式自助餐”,从中挑选出能最好地支持自己希望教授的课程的内容。
2042 0
|
算法
《算法导论(原书第3版)》一思考题
本节书摘来自华章出版社《算法导论(原书第3版)》一 书中的第3章,第3.3节,作者:(美)Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein,更多章节内容可以访问云栖社区“华章计算机”公众号查看。
2385 0