《算法导论》第一讲

简介: 版权声明:您好,转载请留下本人博客的地址,谢谢 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)

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

目录
相关文章
|
算法
数据结构与算法之经典算法《二分查找》
数据结构与算法之经典算法《二分查找》
43 0
|
5月前
|
存储 算法 搜索推荐
算法导论
算法导论
算法导论(第三版)具体算法解析与理解
算法导论(第三版)具体算法解析与理解
|
算法 Java 索引
数据结构与算法之美 | 别怕,有我!KMP 算法详解
为什么我认为 KMP 算法就是个动态规划问题呢,等会再解释。对于动态规划,之前多次强调了要明确 dp 数组的含义,而且同一个问题可能有不止一种定义 dp 数组含义的方法,不同的定义会有不同的解法。
数据结构与算法之美 | 别怕,有我!KMP 算法详解
|
C语言
C语言程序设计——二分查找
C语言程序设计——二分查找
157 0
C语言程序设计——二分查找
|
算法
数据结构与算法 |分支限界法
类似回溯算法,也是一种在问题的解空间树 T 上搜索问题解的算法,但在一般情况下,分支节点界定算法与回溯算法的求解目标不同。回溯法的求解是找出 T 中满足条件约束的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是满足约束条件的解中找出达到某一目标函数值达到极大或极小的解,即在某种意义下的最优解。 ​
368 0
|
算法
数据结构与算法之八皇后问题
八皇后问题代码实现 package com.pionner.recursion; public class Queen8 { int max = 8; int[] array = new int[max]; static int i = 0; public...
792 0
|
算法
算法导论——贪心算法
贪心算法(greedy algorithm)是指,在每一步都做出当时看起来最佳的选择,也就是局部最优的选择,期望这样的选择能够导向全局最优解。所以并不是所有的问题都能得到全局最优解。          典型的例子如分数背包问题:背包容量为50kg,有三个商品分别是重60元/10kg、100元/20kg、120元/30kg,商品可以分割,如何选取商品使背包价值最大。
1505 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的指数级别,导致算法效率低下。
1460 0
|
算法 Python 机器学习/深度学习