Giter Site home page Giter Site logo

learnalgorithm's People

Contributors

sunbigshan avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar

learnalgorithm's Issues

【入门篇】复杂度分析(下)

最后我们再讲几个个复杂度分析方面的知识点:

  • 最好情况时间复杂度
  • 最坏情况时间复杂度
  • 平均情况时间复杂度

最好、最坏情况时间复杂度

话不多说,先看代码:

function find(array, x) {
    let pos = -1;
    for(let i = 0, len = array.length; i < len; i++) {
        if(array[i] === x) {
            pos = i;
        }
    }
    return pos;
}

相信大家都可以看出来,该函数的功能是在一组无序数组中查找元素 x,如果存在,就返回下标,否则返回 -1。按照之前的方法分析,这段代码的时间复杂度为 O(n),其中,n 代表数组的长度。

我们在数组中查找数据,并不需要每次都把数组全部遍历一遍,因为中途就找到目标元素的话就可以提前终止循环了。下面我们再优化一下代码:

function find(array, x) {
    let pos = -1;
    for(let i = 0, len = array.length; i < len; i++) {
        if(array[i] === x) {
            pos = i;
            break;
        }
    }
    return pos;
}

问题来了,我们优化之后的 find 函数的时间复杂度还是 O(n) 吗?很显然不是了,如果我们要查找到元素位于数组的第一个,那么它的时间复杂度就是 O(1),如果位于末尾,那么时间复杂度就是 O(n)。所以,在不同情况下,这段代码的时间复杂度是不一样的。

为了表示代码在不同情况下的不同时间复杂度,我们需要引入三个概念:最好情况时间复杂度最坏情况时间复杂度平均情况时间复杂度

顾名思义,最好情况时间复杂度,就是在最理想的情况下,执行这段代码的时间复杂度。在上述代码中,最理想的情况就是我们要查找的元素 x 正好位于数组的第一位,这时对应的时间复杂度就是最好情况时间复杂度。

同理,最坏情况时间复杂度,就是在最差的情况下,执行这段代码的时间复杂度。还是拿上述例子来说,如果元素 x 不在数组中,我们需要把整个数组都遍历一遍才行,这是对象的时间复杂度就是最坏情况时间复杂度。

平均情况时间复杂度

我们都知道,最好最坏情况时间复杂度都是在极端情况下的时间复杂度,发生的概率其实都不大,为了更准确的表示时间复杂度,我们需要引入第三个概念:平均情况时间复杂度。

还是借助上面的例子,要查找的变量 x 在长度为 n 的数组中的位置,有 n + 1 中情况:在数组 0 ~ n - 1 位置中不在数组中。我们把每种情况下,需要查找遍历的元素个数累加起来(等差数列求和),再除以 n + 1,就可以得到需要遍历元素个数的平均值,即:

image

时间复杂度的大 O 表示法中,可以省略掉系数、低阶、常量。所以,该公式简化之后,可以得到平均情况时间复杂度 O(n)。

【入门篇】复杂度分析(中)

几种常见的时间复杂度案例分析

image

复杂度量级,可以粗略的分为两类:多项式量级非多式量级。其中,非多项式量级只有两个:$O(2^{n})$ 和 $O(n!)$

当数据规模 n 越来越大时,非多项式量级算法的执行时间会急剧增加,求解问题的时间会无限增长。所以,非多项式量级算法是非常低效的,这里我们就不多陈述了。我们主要看下几种常见的多项式量级的时间复杂度。

1. $O(1)$

O(1) 只是一种常见的常量时间复杂度,并不是说只执行了一行代码。比如这段代码,即便有 3 行,它的时间复杂度也是 O(1),而不是 O(3)。

let i = 0;
let j = 0;
let sum = i + j;

总结来说,只要代码的执行时间不随 n 的增大而增长,这样的代码的时间复杂度我们都计作 O(1),或者说,
一般情况下,只要算法中不存在循环语句、递归语句,即便有成千上万行代码,其时间复杂度也是 O(1)

2. $O(logn)$、$O(nlogn)$

对数阶算法复杂度很常见,同时它也是最难分析的一种时间复杂度。举个例子说明一下。

let i = 1;
while(i <= n) {
  i = i * 2;
}

根据前面的时间复杂度分析方法,第三行代码是循环次数最多的。所以,我们只要计算出这行代码被执行了多少次,就能知道整段代码的时间复杂度。

从代码中可以看出,变量 i 的值从 1 开始取,每循环一次就乘以 2。当大于 n 时,循环结束。还记得我们高中学过的等比数列吗?实际上,变量 i 的取值就是一个等比数列。如果我把它一个一个列出来,就应该是这个样子的:

image

所以,我们只要知道 x 值是多少,就知道这行代码执行的次数了。通过 $2^{x}=n$ 求解 x 值我就不多说了,$x=log_2 n$,所以,这段代码的时间复杂度为 $O(log_2 n)$

再稍微修改下代码。

let i = 1;
while(i <= n) {
  i = i * 3;
}

根据之前的思路,我们很简单就可以推算出来,这段代码的时间复杂度为 $O(log_3 n)$

实际上,不管是以 2 为底、以 3 为底,还是以 10 为底,我们可以把所有的对数时间复杂度都计为 $O(logn)$。为什么呢?

我们知道,对数之间是可以互相转换的,$log_3 n = log_3 2 * log_2 n$,所以 $log_3 n=O(C * log_2 n)$,其中 $C=log_3 2$ 是一个常量,基于我们前面的理论:在使用大 O 复杂度表示法的时候,可以忽略常量、低阶、系数,即O(Cf(n)) = O(f(n))。所以,$O(log_3 n)$ 就等于 $O(log_2 n)$。因此,在对数阶时间复杂度中,我们可以忽略对数“底”的存在,统一表示为 $O(logn)$

说到这里,那 $O(nlogn)$ 也就很好理解了吧,还记得我们上篇文章中说的乘法法则吗?如果一段代码的时间复杂度为 $O(logn)$,我们循环了 n 变,时间复杂度就变成了 $O(nlogn)$

$O(nlogn)$ 是一种非常常见的时间复杂度。比如,归并排序、快速排序的时间复杂度都是 $O(nlogn)$

3. O(m+n)、O(m*n)

我们再来讲一种跟前面都不一样的时间复杂度,代码的复杂度由两个数据的规模来决定。老规矩,先看代码!

function cal(m, n) {
    let sum1 = 0;
    let sum2 = 0;
    for(let i = 1; i <= m; i++) {
        sum1 += 1;
    }
    for(let i = 1; i <= n; i++) {
        sum2 += 1;
    }
    return sum1 + sum2;
}

从代码中可以看出,m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大,所以我们在表示复杂度的时候,就不能简单地利用加法法则,省略掉其中一个。所以,上面代码的时间复杂度就是 O(m+n)。

针对这种情况,原来的加法法则就不正确了,我们需要将加法规则改为:T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法则继续有效:T1(m)*T2(n) = O(f(m) * f(n))。

空间复杂度

我们再来回顾一下,时间复杂度的全程为渐进时间复杂度,表示算法执行时间与数据规模之间的增长关系。类比一下,空间复杂度全程就是渐进空间复杂度,表示算法存储空间与数据规模之间的增长关系

function print(n) {
    let a = [];
    for(let i = 0; i < n; i++) {
        a[i] = i * i;
    }
    for(let i = n - 1; i >=0; i--) {
        console.log(a[i]);
    }
}

在上述代码中,我们申请了一个空间存储变量 i,但是它是常量阶的,跟数据规模 n 没有关系,所以忽略。之后又申请了一个大小为 n 的数组,除此之外,剩下的代码没有占用更多的存储空间。所以,这段代码的空间复杂度就是 $O(n)$

我们常见的空间复杂度就是 $O(1)$、$O(n)$、$O(n)$,像 $O(logn)$、$O(nlogn)$ 这样的对数阶复杂度平时都用不到。而且,空间复杂度分析比时间复杂度分析要简单很多。所以,对于空间复杂度,掌握刚我说的这些内容已经足够了。

小结

复杂度也叫渐进复杂度,包括时间复杂度和空间复杂度,用来分析算法执行效率与数据规模之间的增长关系,可以粗略地表示,越高阶复杂度的算法,执行效率越低。常见的复杂度并不多,从低阶到高阶有:$O(1)$、$O(logn)$、$O(n)$、$O(nlogn)$、$O(n^{2})$。

image

【基础篇】栈:如何实现浏览器的前进和后退功能?

浏览器的前进、后退功能,我想你肯定很熟悉吧?

当你依次访问完一串页面 a-b-c 之后,点击浏览器的后退按钮,就可以查看之前浏览过的页面 b 和 a。当你后退到页面 a,点击前进按钮,就可以重新查看页面 b 和 c。但是,如果你后退到页面 b 后,点击了新的页面 d,那就无法再通过前进、后退功能查看页面 c 了。

假设你是 Chrome 浏览器的开发工程师,你会如何实现这个功能呢?

这就要用到我们今天要讲的“栈”这种数据结构。带着这个问题,我们来学习今天的内容。

如何理解“栈”?

关于“栈”,我有一个非常贴切的例子,就是一摞叠在一起的盘子。我们平时放盘子的时候,都是从下往上一个一个放;取的时候,我们也是从上往下一个一个地依次取,不能从中间任意抽出。后进者先出,先进者后出,这就是典型的“栈”结构。

image

从栈的操作特性上来看,栈是一种“操作受限”的线性表,只允许在一端插入和删除数据。

我第一次接触这种数据结构的时候,就对它存在的意义产生了很大的疑惑。因为我觉得,相比数组和链表,栈带给我的只有限制,并没有任何优势。那我直接使用数组或者链表不就好了吗?为什么还要用这个“操作受限”的“栈”呢?

事实上,从功能上来说,数组或链表确实可以替代栈,但你要知道,特定的数据结构是对特定场景的抽象,而且,数组或链表暴露了太多的操作接口,操作上的确灵活自由,但使用时就比较不可控,自然也就更容易出错。

当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,我们就应该首选“栈”这种数据结构

如何实现一个栈

解答开篇

好了,我想现在你已经完全理解了栈的概念。我们再回来看看开篇的思考题,如何实现浏览器的前进、后退功能?其实,用两个栈就可以非常完美地解决这个问题。

我们使用两个栈,X 和 Y,我们把首次浏览的页面依次压入栈 X,当点击后退按钮时,再依次从栈 X 中出栈,并将出栈的数据依次放入栈 Y。当我们点击前进按钮时,我们依次从栈 Y 中取出数据,放入栈 X 中。当栈 X 中没有数据时,那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据,那就说明没有页面可以点击前进按钮浏览了。

比如你顺序查看了 a,b,c 三个页面,我们就依次把 a,b,c 压入栈,这个时候,两个栈的数据就是这个样子:

image

当你通过浏览器的后退按钮,从页面 c 后退到页面 a 之后,我们就依次把 c 和 b 从栈 X 中弹出,并且依次放入到栈 Y。这个时候,两个栈的数据就是这个样子:

image

这个时候你又想看页面 b,于是你又点击前进按钮回到 b 页面,我们就把 b 再从栈 Y 中出栈,放入栈 X 中。此时两个栈的数据是这个样子:

image

这个时候,你通过页面 b 又跳转到新的页面 d 了,页面 c 就无法再通过前进、后退按钮重复查看了,所以需要清空栈 Y。此时两个栈的数据这个样子:

image

【基础篇】数组:为什么很多编程语言中数组都是从0开始编号?

在每一种编程语言中,基本都会有数组这种数据类型。不过,它不仅仅是一种编程语言中的数据类型,还是一种最基础的数据结构。尽管数组看起来非常基础、简单,但是我估计很多人都并没有理解这个基础数据结构的精髓。

在大部分编程语言中,数组都是从 0 开始编号的,但你是否下意识地想过,为什么数组要从 0 开始编号,而不是从 1 开始呢? 从 1 开始不是更符合人类的思维习惯吗?

如何实现随机访问?

什么是数组?我们用专业的术语来做下解析。

数组(Array)是一种线性表数据结构。它是一组连续的内存空间,来存储一组具有相同类型的数据。

这里我们来分析几个关键词。

第一,线性表(Linear List)。顾名思义,线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组,链表、队列、栈等也是线性表结构。

image

而与它相对立是的非线性表,比如二叉树、堆、图等。之所以叫非线性,是因为,在非线性表中,数据之间并不是简单的前后关系。

image

第二个是连续的空间和相同的数据类型。正是因为这两个限制,它才有了一个堪称“杀手锏”的特性:“随机访问”。但有利就有弊,这两个限制也让数组的很多操作变得非常低效,比如要想在数组中删除、插入一个数据,为了保证连续性,就需要做大量的数据搬移工作。

说到数据的访问,那你知道数组是如何实现根据下标随机访问数组元素的吗?

我们拿一个长度为 10 的 int 类型的数组 int[] a = new int[10] 来举例。在我画的这个图中,计算机给数组 a[10],分配了一块连续内存空间 1000~1039,其中,内存块的首地址为 base_address = 1000。

image

我们知道,计算机会给每个内存单元分配一个地址,计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素存储的内存地址:

a[i]_address = base_address + i * data_type_size

其中 data_type_size 表示数组中每个元素的大小。我们举的这个例子里,数组中存储的是 int 类型数据,所以 data_type_size 就为 4 个字节。

我们在面试的时候,常常会被问数组和链表的区别,很多人都回答说,“链表适合插入、删除,时间复杂度 O(1);数组适合查找,查找时间复杂度为 O(1)”。

实际上,这种表述是不准确的。数组是适合查找操作,但是查找的时间复杂度并不为 O(1)。即便是排好序的数组,你用二分查找,时间复杂度也是 O(logn)。所以,正确的表述应该是,数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)。

低效的“插入”和“删除”

假设数组的长度为 n,现在,如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来,给新来的数据,我们需要将第 k~n 这部分的元素都顺序地往后挪一位。那插入操作的时间复杂度是多少呢?你可以自己先试着分析一下。

如果在数组的末尾插入元素,那就不需要移动数据了,这时的时间复杂度为 O(1)。但如果在数组的开头插入元素,那所有的数据都需要依次往后移动一位,所以最坏时间复杂度是 O(n)。 因为我们在每个位置插入元素的概率是一样的,所以平均情况时间复杂度为 (1+2+…n)/n=O(n)。

如果数组中的数据是有序的,我们在某个位置插入一个新的元素时,就必须按照刚才的方法搬移 k 之后的数据。但是,如果数组中存储的数据并没有任何规律,数组只是被当作一个存储数据的集合。在这种情况下,如果要将某个数组插入到第 k 个位置,为了避免大规模的数据搬移,我们还有一个简单的办法就是,直接将第 k 位的数据搬移到数组元素的最后,把新的元素直接放入第 k 个位置。

为了更好地理解,我们举一个例子。假设数组 a[10] 中存储了如下 5 个元素:a,b,c,d,e。

我们现在需要将元素 x 插入到第 3 个位置。我们只需要将 c 放入到 a[5],将 a[2] 赋值为 x 即可。最后,数组中的元素如下: a,b,x,d,e,c。

image

利用这种处理技巧,在特定场景下,在第 k 个位置插入一个元素的时间复杂度就会降为 O(1)。这个处理**在快排中也会用到,后续会在排序中说到。

我们再来看删除操作。

跟插入数据类似,如果我们要删除第 k 个位置的数据,为了内存的连续性,也需要搬移数据,不然中间就会出现空洞,内存就不连续了。

和插入类似,如果删除数组末尾的数据,则最好情况时间复杂度为 O(1);如果删除开头的数据,则最坏情况时间复杂度为 O(n);平均情况时间复杂度也为 O(n)。

实际上,在某些特殊场景下,我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行,删除的效率是不是会提高很多呢?

我们继续来看例子。数组 a[10] 中存储了 8 个元素:a,b,c,d,e,f,g,h。现在,我们要依次删除 a,b,c 三个元素。

image

为了避免 d,e,f,g,h 这几个数据会被搬移三次,我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据,只是记录数据已经被删除。当数组没有更多空间存储数据时,我们再触发执行一次真正的删除操作,这样就大大减少了删除操作导致的数据搬移。

如果你了解 JVM,你会发现,这不就是 JVM 标记清除垃圾回收算法的核心**吗?没错,数据结构和算法的魅力就在于此,很多时候我们并不是要去死记硬背某个数据结构或者算法,而是要学习它背后的**和处理技巧,这些东西才是最有价值的。如果你细心留意,不管是在软件开发还是架构设计中,总能找到某些算法和数据结构的影子。

解答开篇

现在我们来思考开篇的问题:为什么大多数编程语言中,数组要从 0 开始编号,而不是从 1 开始呢?

从数组存储的内存模型上来看,“下标”最确切的定义应该是“偏移(offset)”。前面也讲到,如果用 a 来表示数组的首地址,a[0] 就是偏移为 0 的位置,也就是首地址,a[k] 就表示偏移 k 个 type_size 的位置,所以计算 a[k] 的内存地址只需要用这个公式:

a[k]_address = base_address + k * type_size

但是,如果数组从 1 开始计数,那我们计算数组元素 a[k] 的内存地址就会变为:

a[k]_address = base_address + (k-1) * type_size

对比两个公式,我们不难发现,从 1 开始编号,每次随机访问数组元素都多了一次减法运算,对于 CPU 来说,就是多了一次减法指令。

数组作为非常基础的数据结构,通过下标随机访问数组元素又是其非常基础的编程操作,效率的优化就要尽可能做到极致。所以为了减少一次减法操作,数组选择了从 0 开始编号,而不是从 1 开始。

不过我认为,上面解释得再多其实都算不上压倒性的证明,说数组起始编号非 0 开始不可。所以我觉得最主要的原因可能是历史原因。

C 语言设计者用 0 开始计数数组下标,之后的 Java、JavaScript 等高级语言都效仿了 C 语言,或者说,为了在一定程度上减少 C 语言程序员学习 Java 的学习成本,因此继续沿用了从 0 开始计数的习惯。实际上,很多语言中数组也并不是从 0 开始计数的,比如 Matlab。甚至还有一些语言支持负数下标,比如 Python。

小结

我们今天学习了数组。它可以说是最基础、最简单的数据结构了。数组用一块连续的内存空间,来存储相同类型的一组数据,最大的特点就是支持随机访问,但插入、删除操作也因此变得比较低效,平均情况时间复杂度为 O(n)。

【基础篇】排序:冒泡、插入、选择

冒泡排序(Bubble Sort)

我们从冒泡排序开始,学习今天的三种排序算法。

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。

我用一个例子,带你看下冒泡排序的整个过程。我们要对一组数据 4,5,6,3,2,1,从小到到大进行排序。第一次冒泡操作的详细过程就是这样:

image

可以看出,经过一次冒泡操作之后,6 这个元素已经存储在正确的位置上。要想完成所有数据的排序,我们只要进行 6 次这样的冒泡操作就行了。

image

实际上,刚讲的冒泡过程还可以优化。当某次冒泡操作已经没有数据交换时,说明已经达到完全有序,不用再继续执行后续的冒泡操作。我这里还有另外一个例子,这里面给 6 个元素排序,只需要 4 次冒泡操作就可以了。

image

冒泡排序算法的原理比较容易理解,具体的代码我贴到下面,你可以结合着代码来看我前面讲的原理。

/**
 * 冒泡排序
 */
const bubbleSort = (arr) => {
    if(arr.length <= 1) return;
    const len = arr.length;
    for(let i = 0; i < len; i++) {
        let hasChange = false;
        for(let j = 0; j < len - i - 1; j++) {
            if(arr[j] > arr[j + 1]) {
                const temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
                hasChange = true;
            }
        }
        if(!hasChange) break;
    }
    console.log(arr);
}

现在,结合刚才我分析排序算法的三个方面,我有三个问题要问你。

第一,冒泡排序是原地排序算法吗?

冒泡的过程只涉及相邻数据的交换操作,只需要常量级的临时空间,所以它的空间复杂度为 O(1),是一个原地排序算法。

第二,冒泡排序是稳定的排序算法吗?

在冒泡排序中,只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性,当有相邻的两个元素大小相等的时候,我们不做交换,相同大小的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法。

第三,冒泡排序的时间复杂度是多少?

最好情况下,要排序的数据已经是有序的了,我们只需要进行一次冒泡操作,就可以结束了,所以最好情况时间复杂度是 O(n)。而最坏的情况是,要排序的数据刚好是倒序排列的,我们需要进行 n 次冒泡操作,所以最坏情况时间复杂度为 $O(n^{2})$

image

最好、最坏情况下的时间复杂度很容易分析,那平均情况下的时间复杂是多少呢?我们前面讲过,平均时间复杂度就是加权平均期望时间复杂度,分析的时候要结合概率论的知识。

对于包含 n 个数据的数组,这 n 个数据就有 n! 种排列方式。不同的排列方式,冒泡排序执行的时间肯定是不同的。比如我们前面举的那两个例子,其中一个要进行 6 次冒泡,而另一个只需要 4 次。如果用概率论方法定量分析平均时间复杂度,涉及的数学推理和计算就会很复杂。我这里还有一种思路,通过“有序度”和“逆序度”这两个概念来进行分析。

有序度是数组中具有有序关系的元素对的个数。有序元素对用数学表达式表示就是这样:

有序元素对:a[i] <= a[j], 如果 i < j。

image

同理,对于一个倒序排列的数组,比如 6,5,4,3,2,1,有序度是 0;对于一个完全有序的数组,比如 1,2,3,4,5,6,有序度就是n*(n-1)/2,也就是 15。我们把这种完全有序的数组的有序度叫作满有序度

逆序度的定义正好跟有序度相反(默认从小到大为有序),我想你应该已经想到了。关于逆序度,我就不举例子讲了。你可以对照我讲的有序度的例子自己看下。

逆序元素对:a[i] > a[j], 如果 i < j。

关于这三个概念,我们还可以得到一个公式:逆序度 = 满有序度 - 有序度。我们排序的过程就是一种增加有序度,减少逆序度的过程,最后达到满有序度,就说明排序完成了。

我还是拿前面举的那个冒泡排序的例子来说明。要排序的数组的初始状态是 4,5,6,3,2,1 ,其中,有序元素对有 (4,5) (4,6)(5,6),所以有序度是 3。n=6,所以排序完成之后终态的满有序度为 n*(n-1)/2=15。

image

冒泡排序包含两个操作原子,比较和交换。每交换一次,有序度就加 1。不管算法怎么改进,交换次数总是确定的,即为逆序度,也就是n*(n-1)/2–初始有序度。此例中就是 15–3=12,要进行 12 次交换操作。

对于包含 n 个数据的数组进行冒泡排序,平均交换次数是多少呢?最坏情况下,初始状态的有序度是 0,所以要进行 n*(n-1)/2 次交换。最好情况下,初始状态的有序度是 n*(n-1)/2,就不需要进行交换。我们可以取个中间值 n*(n-1)/4,来表示初始有序度既不是很高也不是很低的平均情况。

换句话说,平均情况下,需要 n*(n-1)/4 次交换操作,比较操作肯定要比交换操作多,而复杂度的上限是 $O(n^{2})$,所以平均情况下的时间复杂度就是 $O(n^{2})$

这个平均时间复杂度推导过程其实并不严格,但是很多时候很实用,毕竟概率论的定量分析太复杂,不太好用。

插入排序(Insertion Sort)

我们先来看一个问题。一个有序的数组,我们往里面添加一个新的数据后,如何继续保持数据有序呢?很简单,我们只要遍历数组,找到数据应该插入的位置将其插入即可。

image

这是一个动态排序的过程,即动态地往有序集合中添加数据,我们可以通过这种方法保持集合中的数据一直有序。而对于一组静态数据,我们也可以借鉴上面讲的插入方法,来进行排序,于是就有了插入排序算法。

那插入排序具体是如何借助上面的**来实现排序的呢?

首先,我们将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心**是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。

如图所示,要排序的数据是 4,5,6,1,3,2,其中左侧为已排序区间,右侧是未排序区间。

image

插入排序也包含两种操作,一种是元素的比较,一种是元素的移动。当我们需要将一个数据 a 插入到已排序区间时,需要拿 a 与已排序区间的元素依次比较大小,找到合适的插入位置。找到插入点之后,我们还需要将插入点之后的元素顺序往后移动一位,这样才能腾出位置给元素 a 插入。

对于不同的查找插入点方法(从头到尾、从尾到头),元素的比较次数是有区别的。但对于一个给定的初始序列,移动操作的次数总是固定的,就等于逆序度。

为什么说移动次数就等于逆序度呢?我拿刚才的例子画了一个图表,你一看就明白了。满有序度是 n*(n-1)/2=15,初始序列的有序度是 5,所以逆序度是 10。插入排序中,数据移动的个数总和也等于 10=3+3+4。

image

插入排序的原理也很简单吧?我也将代码实现贴在这里,你可以结合着代码再看下。

/**
 * 插入排序
 */
const insertionSort = (arr) => {
    if(arr.length <= 1) return;
    const len = arr.length;
    for(let i = 1; i < len; i++) {
        const temp = arr[i];
        let j = i - 1;
        for(; j >= 0; j--) {
            if(arr[j] > temp) {
                arr[j + 1] = arr[j];
            }else{
                break;
            }
        }
        arr[j + 1] = temp;
    }
    console.log(arr);
}

现在,我们来看点稍微复杂的东西。我这里还是有三个问题要问你。

第一,插入排序是原地排序算法吗?

从实现过程可以很明显地看出,插入排序算法的运行并不需要额外的存储空间,所以空间复杂度是 O(1),也就是说,这是一个原地排序算法。

第二,插入排序是稳定的排序算法吗?

在插入排序中,对于值相同的元素,我们可以选择将后面出现的元素,插入到前面出现元素的后面,这样就可以保持原有的前后顺序不变,所以插入排序是稳定的排序算法。

第三,插入排序的时间复杂度是多少?

如果要排序的数据已经是有序的,我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置,每次只需要比较一个数据就能确定插入的位置。所以这种情况下,最好是时间复杂度为 O(n)。注意,这里是从尾到头遍历已经有序的数据。

如果数组是倒序的,每次插入都相当于在数组的第一个位置插入新的数据,所以需要移动大量的数据,所以最坏情况时间复杂度为 $O(n^{2})$

还记得我们在数组中插入一个数据的平均时间复杂度是多少吗?没错,是 O(n)。所以,对于插入排序来说,每次插入操作都相当于在数组中插入一个数据,循环执行 n 次插入操作,所以平均时间复杂度为 $O(n^{2})$

选择排序(Selection Sort)

选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。

image

代码如下:

/**
 * 选择排序
 */
const selectionSort = (arr) => {
    if(arr.length <= 1) return;
    const len = arr.length;
    for(let i = 0; i < len - 1; i++) {
        let minIndex = i;
        for(let j = i + 1; j < len; j++) {
            if(arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        const temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    console.log(arr);
}

照例,也有三个问题需要你思考,不过前面两种排序算法我已经分析得很详细了,这里就直接公布答案了。

首先,选择排序空间复杂度为 O(1),是一种原地排序算法。选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 $O(n^{2})$。你可以自己来分析看看。

那选择排序是稳定的排序算法吗?这个问题我着重来说一下。

答案是否定的,选择排序是一种不稳定的排序算法。从我前面画的那张图中,你可以看出来,选择排序每次都要找剩余未排序元素中的最小值,并和前面的元素交换位置,这样破坏了稳定性。

比如 5,8,5,2,9 这样一组数据,使用选择排序算法来排序的话,第一次找到最小元素 2,与第一个 5 交换位置,那第一个 5 和中间的 5 顺序就变了,所以就不稳定了。正是因此,相对于冒泡排序和插入排序,选择排序就稍微逊色了。

解答开篇

基本的知识都讲完了,我们来看开篇的问题:冒泡排序和插入排序的时间复杂度都是 $O(n^{2})$,都是原地排序算法,为什么插入排序要比冒泡排序更受欢迎呢?

我们前面分析冒泡排序和插入排序的时候讲到,冒泡排序不管怎么优化,元素交换的次数是一个固定值,是原始数据的逆序度。插入排序是同样的,不管怎么优化,元素移动的次数也等于原始数据的逆序度。

但是,从代码实现上来看,冒泡排序的数据交换要比插入排序的数据移动要复杂,冒泡排序需要 3 个赋值操作,而插入排序只需要 1 个。我们来看这段操作:

// 冒泡排序中数据的交换操作:
if(arr[j] > arr[j + 1]) {
  const temp = arr[j + 1];
  arr[j + 1] = arr[j];
  arr[j] = temp;
  hasChange = true;
}

// 插入排序中数据的移动操作:
if(arr[j] > temp) {
  arr[j + 1] = arr[j];
}else{
  break;
}

我们把执行一个赋值语句的时间粗略地计为单位时间(unit_time),然后分别用冒泡排序和插入排序对同一个逆序度是 K 的数组进行排序。用冒泡排序,需要 K 次交换操作,每次需要 3 个赋值语句,所以交换操作总耗时就是 3*K 单位时间。而插入排序中数据移动操作只需要 K 个单位时间。

这个只是我们非常理论的分析,为了实验,针对上面的冒泡排序和插入排序的 Java 代码,我写了一个性能对比测试程序,随机生成 10000 个数组,每个数组中包含 200 个数据,然后在我的机器上分别用冒泡和插入排序算法来排序,冒泡排序算法大约 700ms 才能执行完成,而插入排序只需要 100ms 左右就能搞定!

所以,虽然冒泡排序和插入排序在时间复杂度上是一样的,都是 $O(n^{2})$,但是如果我们希望把性能优化做到极致,那肯定首选插入排序。插入排序的算法思路也有很大的优化空间,我们只是讲了最基础的一种。如果你对插入排序的优化感兴趣,可以自行学习一下希尔排序。

内容小结

要想分析、评价一个排序算法,需要从执行效率、内存消耗和稳定性三个方面来看。因此,这一节,我带你分析了三种时间复杂度是 $O(n^{2})$ 的排序算法,冒泡排序、插入排序、选择排序。你需要重点掌握的是它们的分析方法。

image

这三种时间复杂度为 $O(n^{2})$ 的排序算法中,冒泡排序、选择排序,可能就纯粹停留在理论的层面了,学习的目的也只是为了开拓思维,实际开发中应用并不多,但是插入排序还是挺有用的。后面讲排序优化的时候,我会讲到,有些编程语言中的排序函数的实现原理会用到插入排序算法。

今天讲的这三种排序算法,实现代码都非常简单,对于小规模数据的排序,用起来非常高效。但是在大规模数据排序的时候,这个时间复杂度还是稍微有点高,所以我们更倾向于用下一节要讲的时间复杂度为 $O(nlogn)$ 的排序算法。

【基础篇】如何分析一个排序算法?

排序对于任何一个程序员来说,可能都不会陌生。你学的第一个算法,可能就是排序。大部分编程语言中,也都提供了排序函数。在平常的项目中,我们也经常会用到排序。排序非常重要,所以我会花多一点时间来详细讲一讲经典的排序算法。

排序算法太多了,有很多可能你连名字都没听说过,比如猴子排序、睡眠排序、面条排序等。我只讲众多排序算法中的一小撮,也是最经典的、最常用的:冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。我按照时间复杂度把它们分成了三类,分三节课来讲解。

image

带着问题去学习,是最有效的学习方法。所以按照惯例,我还是先给你出一个思考题:

插入排序和冒泡排序的时间复杂度相同,都是 $O(n^{2})$,在实际的软件开发里,为什么我们更倾向于使用插入排序算法而不是冒泡排序算法呢?

你可以先思考一两分钟,带着这个问题,我们开始今天的内容!

如何分析一个“排序算法”?

学习排序算法,我们除了学习它的算法原理、代码实现之外,更重要的是要学会如何评价、分析一个排序算法。那分析一个排序算法,要从哪几个方面入手呢?

排序算法的执行效率

对于排序算法执行效率的分析,我们一般会从这几个方面来衡量:

1. 最好情况、最坏情况、平均时间复杂度

我们在分析排序算法的时间复杂度时,要分别给出最好情况、最坏情况、平均情况下的时间复杂度。除此之外,你还要说出最好、最坏时间复杂度对应的要排序的原始数据是什么样的。

为什么要区分这三种时间复杂度呢?第一,有些排序算法会区分,为了好对比,所以我们最好都做一下区分。第二,对于要排序的数据,有的接近有序,有的完全无序。有序度不同的数据,对于排序的执行时间肯定是有影响的,我们要知道排序算法在不同数据下的性能表现。

2. 时间复杂度的系数、常数 、低阶

我们知道,时间复杂度反应的是数据规模 n 很大的时候的一个增长趋势,所以它表示的时候会忽略系数、常数、低阶。但是实际的软件开发中,我们排序的可能是 10 个、100 个、1000 个这样规模很小的数据,所以,在对同一阶时间复杂度的排序算法性能对比的时候,我们就要把系数、常数、低阶也考虑进来。

3. 比较次数和交换(或移动)次数

这一节和下一节讲的都是基于比较的排序算法。基于比较的排序算法的执行过程,会涉及两种操作,一种是元素比较大小,另一种是元素交换或移动。所以,如果我们在分析排序算法的执行效率的时候,应该把比较次数和交换(或移动)次数也考虑进去。

排序算法的内存消耗

我们前面讲过,算法的内存消耗可以通过空间复杂度来衡量,排序算法也不例外。不过,针对排序算法的空间复杂度,我们还引入了一个新的概念,原地排序(Sorted in place)。原地排序算法,就是特指空间复杂度是 O(1) 的排序算法。我们今天讲的三种排序算法,都是原地排序算法。

排序算法的稳定性

仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法,我们还有一个重要的度量指标,稳定性。这个概念是说,如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。

我通过一个例子来解释一下。比如我们有一组数据 2,9,3,4,8,3,按照大小排序之后就是 2,3,3,4,8,9。

这组数据里有两个 3。经过某种排序算法排序之后,如果两个 3 的前后顺序没有改变,那我们就把这种排序算法叫作稳定的排序算法;如果前后顺序发生变化,那对应的排序算法就叫作不稳定的排序算法

你可能要问了,两个 3 哪个在前,哪个在后有什么关系啊,稳不稳定又有什么关系呢?为什么要考察排序算法的稳定性呢?

很多数据结构和算法课程,在讲排序的时候,都是用整数来举例,但在真正软件开发中,我们要排序的往往不是单纯的整数,而是一组对象,我们需要按照对象的某个 key 来排序。

比如说,我们现在要给电商交易系统中的“订单”排序。订单有两个属性,一个是下单时间,另一个是订单金额。如果我们现在有 10 万条订单数据,我们希望按照金额从小到大对订单数据排序。对于金额相同的订单,我们希望按照下单时间从早到晚有序。对于这样一个排序需求,我们怎么来做呢?

最先想到的方法是:我们先按照金额对订单数据进行排序,然后,再遍历排序之后的订单数据,对于每个金额相同的小区间再按照下单时间排序。这种排序思路理解起来不难,但是实现起来会很复杂。

借助稳定排序算法,这个问题可以非常简洁地解决。解决思路是这样的:我们先按照下单时间给订单排序,注意是按照下单时间,不是金额。排序完成之后,我们用稳定排序算法,按照订单金额重新排序。两遍排序之后,我们得到的订单数据就是按照金额从小到大排序,金额相同的订单按照下单时间从早到晚排序的。为什么呢?

稳定排序算法可以保持金额相同的两个对象,在排序之后的前后顺序不变。第一次排序之后,所有的订单按照下单时间从早到晚有序了。在第二次排序中,我们用的是稳定的排序算法,所以经过第二次排序之后,相同金额的订单仍然保持下单时间从早到晚有序。

image

【基础篇】递归:如何理解递归?

递归是一种应用非常广泛的算法(或者编程技巧)。之后我们要讲的很多数据结构和算法的编码实现都要用到递归,比如 DFS 深度优先搜索、前中后序二叉树遍历等等。所以,搞懂递归非常重要,否则,后面复杂一些的数据结构和算法学起来就会比较吃力。

不过,别看我说了这么多,递归本身可是一点儿都不“高冷”,咱们生活中就有很多用到递归的例子。

周末你带着女朋友去电影院看电影,女朋友问你,咱们现在坐在第几排啊?电影院里面太黑了,看不清,没法数,现在你怎么办?

别忘了你是程序员,这个可难不倒你,递归就开始排上用场了。于是你就问前面一排的人他是第几排,你想只要在他的数字上加一,就知道自己在哪一排了。但是,前面的人也看不清啊,所以他也问他前面的人。就这样一排一排往前问,直到问到第一排的人,说我在第一排,然后再这样一排一排再把数字传回来。直到你前面的人告诉你他在哪一排,于是你就知道答案了。

这就是一个非常标准的递归求解问题的分解过程,去的过程叫“递”,回来的过程叫“归”。基本上,所有的递归问题都可以用递推公式来表示。刚刚这个生活中的例子,我们用递推公式将它表示出来就是这样的:

f(n) = f(n-1)+1 其中 f(1) = 1

f(n) 表示你想知道自己在哪一排,f(n-1) 表示前面一排所在的排数,f(1)=1 表示第一排的人知道自己在第一排。有了这个递推公式,我们就可以很轻松地将它改为递归代码,如下:

function f(n) {
  if(n === 1) return 1;
  return f(n-1)+1;
}

递归需要满足的三个条件

刚刚这个例子是非常典型的递归,那究竟什么样的问题可以用递归来解决呢?我总结了三个条件,只要同时满足以下三个条件,就可以用递归来解决。

1. 一个问题的解可以分解为几个子问题的解

何为子问题?子问题就是数据规模更小的问题。比如,前面讲的电影院的例子,你要知道,“自己在哪一排”的问题,可以分解为“前一排的人在哪一排”这样一个子问题。

2. 这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样

比如电影院那个例子,你求解“自己在哪一排”的思路,和前面一排人求解“自己在哪一排”的思路,是一模一样的。

3. 存在递归终止条件

把问题分解为子问题,把子问题再分解为子子问题,一层一层分解下去,不能存在无限循环,这就需要有终止条件。

还是电影院的例子,第一排的人不需要再继续询问任何人,就知道自己在哪一排,也就是 f(1)=1,这就是递归的终止条件。

如何编写递归代码?

刚刚铺垫了这么多,现在我们来看,如何来写递归代码?我个人觉得,写递归代码最关键的是写出递推公式,找到终止条件,剩下将递推公式转化为代码就很简单了。

你先记住这个理论。我举一个例子,带你一步一步实现一个递归代码,帮你理解。

假如这里有 n 个台阶,每次你可以跨 1 个台阶或者 2 个台阶,请问走这 n 个台阶有多少种走法?如果有 7 个台阶,你可以 2,2,2,1 这样子上去,也可以 1,2,1,1,2 这样子上去,总之走法有很多,那如何用编程求得总共有多少种走法呢?

我们仔细想下,实际上,可以根据第一步的走法把所有走法分为两类,第一类是第一步走了 1 个台阶,另一类是第一步走了 2 个台阶。所以 n 个台阶的走法就等于先走 1 阶后,n-1 个台阶的走法 加上先走 2 阶后,n-2 个台阶的走法。用公式表示就是:

f(n) = f(n-1)+f(n-2)

有了递推公式,递归代码基本上就完成了一半。我们再来看下终止条件。当有一个台阶时,我们不需要再继续递归,就只有一种走法。所以 f(1)=1。这个递归终止条件足够吗?我们可以用 n=2,n=3 这样比较小的数试验一下。

n=2 时,f(2)=f(1)+f(0)。如果递归终止条件只有一个 f(1)=1,那 f(2) 就无法求解了。所以除了 f(1)=1 这一个递归终止条件外,还要有 f(0)=1,表示走 0 个台阶有一种走法,不过这样子看起来就不符合正常的逻辑思维了。所以,我们可以把 f(2)=2 作为一种终止条件,表示走 2 个台阶,有两种走法,一步走完或者分两步来走。

所以,递归终止条件就是 f(1)=1,f(2)=2。这个时候,你可以再拿 n=3,n=4 来验证一下,这个终止条件是否足够并且正确。

我们把递归终止条件和刚刚得到的递推公式放到一起就是这样的:

f(1) = 1;
f(2) = 2;
f(n) = f(n-1)+f(n-2)

有了这个公式,我们转化成递归代码就简单多了。最终的递归代码是这样的:

function f(n) {
  if(n === 1 || n === 2) {
    return n;
  }
  return f(n-1) + f(n-2)
}

写递归代码的关键就是找到如何将大问题分解为小问题的规律,并且基于此写出递推公式,然后再推敲终止条件,最后将递推公式和终止条件翻译成代码

递归代码要警惕堆栈溢出

如果忘记加上用以停止函数递归调用的边界条件,会发生什么呢?递归并不会无限地执行下去;浏览器会抛出错误,也就是所谓的栈溢出错误(stack overflow error)。

ECMAScript 6有尾调用优化(tail call optimization)。如果函数内最后一个操作是调用函数(就像示例中加粗的那行),会通过“跳转指令”(jump) 而不是“子程序调用”(subroutine call)来控制。也就是说,在ECMAScript 6中,这里的代码可以一直执行下去。所以,具有停止递归的边界条件非常重要。

有兴趣的同学可以看下我的另一篇文章:

递归代码要警惕重复计算

除此之外,使用递归时还会出现重复计算的问题。刚才我讲的第二个递归代码的例子,如果我们把整个递归过程分解一下的话,那就是这样的:

image

从图中,我们可以直观地看到,想要计算 f(5),需要先计算 f(4) 和 f(3),而计算 f(4) 还需要计算 f(3),因此,f(3) 就被计算了很多次,这就是重复计算问题。

为了避免重复计算,我们可以通过一个数据结构(比如散列表)来保存已经求解过的 f(k)。当递归调用到 f(k) 时,先看下是否已经求解过了。如果是,则直接从散列表中取值返回,不需要重复计算,这样就能避免刚讲的问题了。

按照上面的思路,我们来改造一下刚才的代码:

const hasSovledList = new Map();

function f(n) {
  if(n === 1 || n === 2) {
    return n;
  }

  if(hasSovledList.has(n)) {
    return hasSovledList.get(n);
  }

  let ret = f(n-1) + f(n-2);
  hasSovledList.set(n, ret);
  return ret;
}

除了堆栈溢出、重复计算这两个常见的问题。递归代码还有很多别的问题。

在时间效率上,递归代码里多了很多函数调用,当这些函数调用的数量较大时,就会积聚成一个可观的时间成本。在空间复杂度上,因为递归调用一次就会在内存栈中保存一次现场数据,所以在分析递归代码空间复杂度时,需要额外考虑这部分的开销,比如我们前面讲到的电影院递归代码,空间复杂度并不是 O(1),而是 O(n)。

内容小结

递归是一种非常高效、简洁的编码技巧。只要是满足“三个条件”的问题就可以通过递归代码来解决。

不过递归代码也比较难写、难理解。编写递归代码的关键就是不要把自己绕进去,正确姿势是写出递推公式,找出终止条件,然后再翻译成递归代码。

不过递归代码也比较难写、难理解。编写递归代码的关键就是不要把自己绕进去,正确姿势是写出递推公式,找出终止条件,然后再翻译成递归代码。

【基础篇】排序:快速排序

快速排序也许是最常用的排序算法了。它的复杂度为O(nlogn),且它的性能通常比其他的复杂度为O(nlogn)的排序算法要好。和归并排序一样,快速排序也使用分治的方法,将原始数组分为较小的数组(但它没有像归并排序那样将它们分割开)。

快速排序比到目前为止你学过的其他排序算法要复杂一些。让我们一步步地来学习。

(1) 首先,从数组中选择中间一项作为主元。

(2) 创建两个指针,左边一个指向数组第一个项,右边一个指向数组最后一个项。移动左指针直到我们找到一个比主元大的元素,接着,移动右指针直到找到一个比主元小的元素,然后交换它们,重复这个过程,直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前,而比主元大的值都排在主元之后。这一步叫作划分操作。

(3) 接着,算法对划分后的小数组(较主元小的值组成的子数组,以及较主元大的值组成的子数组)重复之前的两个步骤,直至数组已完全排序。

让我们开始快速排序的实现吧:

this.quickSort = function(){
  quick(array,  0, array.length - 1);
};

就像归并算法那样,开始我们声明一个主方法来调用递归函数,传递待排序数组,以及索引0及其最末的位置(因为我们要排整个数组,而不是一个子数组)作为参数。

var quick = function(array, left, right){

  var index; //{1}

  if (array.length > 1) { //{2}

    index = partition(array, left, right); //{3}

    if (left < index - 1) {                //{4}
      quick(array, left, index - 1);     //{5}
    }

    if (index < right) {  //{6}
      quick(array, index, right);        //{7}
    }
  }
};

首先声明index(行{1}),该变量能帮助我们将子数组分离为较小值数组和较大值数组,这样,我们就能再次递归的调用quick函数了。partition函数返回值将赋值给index(行{3})。

如果数组的长度比1大(因为只有一个元素的数组必然是已排序了的(行{2}),我们将对给定子数组执行partition操作(第一次调用是针对整个数组)以得到index(行{3})。如果子数组存在较小值的元素(行{4}),则对该数组重复这个过程(行{5})。同理,对存在较大值得子数组也是如此,如果存在子数组存在较大值,我们也将重复快速排序过程(行{7})。

划分过程

第一件要做的事情是选择主元(pivot),有好几种方式。最简单的一种是选择数组的第一项(最左项)。然而,研究表明对于几乎已排序的数组,这不是一个好的选择,它将导致该算法的最差表现。另外一种方式是随机选择一个数组项或是选择中间项。

现在,让我们看看划分过程:

var partition = function(array, left, right) {
 
  var pivot = array[Math.floor((right + left) / 2)], //{8}
    i = left,                                      //{9}
    j = right;                                     //{10}
 
  while (i <= j) {                //{11}
    while (array[i] < pivot) {  //{12}
      i++;
    }
    while (array[j] > pivot) {  //{13}
      j--;
    }
    if (i <= j) { //{14}
      swap(array, i, j); //{15}
      i++;
      j--;
    }
  }
  return i; //{16}
};

在本实现中,我们选择中间项作为主元(行{8})。我们初始化两个指针:left(低——行{9}),初始化为数组第一个元素;right(高——行{10}),初始化为数组最后一个元素。

只要left和right指针没有相互交错(行{11}),就执行划分操作。首先,移动left指针直到找到一个元素比主元大(行{12})。对right指针,我们做同样的事情,移动right指针直到我们找到一个元素比主元小。

当左指针指向的元素比主元大且右指针指向的元素比主元小,并且此时左指针索引没有右指针索引大(行{14}),意思是左项比右项大(值比较)。我们交换它们,然后移动两个指针,并重复此过程(从行{11}再次开始)。

在划分操作结束后,返回左指针的索引,用来在行{3}处创建子数组。

swap函数代码如下:

[array[index1], array[index2]] = [array[index2], array[index1]];

【基础篇】链表:如何实现LRU缓存淘汰算法?

今天我们来学习一下“链表(Linked list)”这个数据结构。学习链表有什么用呢?为了回答这个问题,我们先来讨论下链表的经典应用场景,那就是 LRU 缓存淘汰算法

缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。

缓存的大小有限,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留?这就需要缓存淘汰策略来决定。常见的策略有三种:先进先出策略 FIFO(First In,First Out)、最少使用策略 LFU(Least Frequently Used)、最近最少使用策略 LRU(Least Recently Used)。

这些策略你不用死记,我打个比方你很容易就明白了。假如说,你买了很多本技术书,但有一天你发现,这些书太多了,太占书房空间了,你要做个大扫除,扔掉一些书籍。那这个时候,你会选择扔掉哪些书呢?对应一下,你的选择标准是不是和上面的三种策略神似呢?

好了,回到正题,我们今天的开篇问题就是:如何用链表来实现 LRU 缓存淘汰策略呢? 带着这个问题,我们开始今天的内容吧!

五花八门的链表结构

相比数组,链表是一种稍微复杂一点的数据结构。对于初学者来说,掌握起来也要比数组稍难一些。这两个非常基础、非常常用的数据结构,我们常常将会放到一块儿来比较。所以我们先来看,这两者有什么区别。

我们先从底层的存储结构上来看一看。

为了直观地对比,我画了一张图。从图中我们看到,数组需要一块连续的内存空间来存储,对内存的要求比较高。如果我们申请一个 100MB 大小的数组,当内存中没有连续的、足够大的存储空间时,即便内存的剩余总可用空间大于 100MB,仍然会申请失败。

而链表恰恰相反,它并不需要一块连续的内存空间,它通过“指针”将一组零散的内存块串联起来使用,所以如果我们申请的是 100MB 大小的链表,根本不会有问题。

image

单链表

image

链表的第一个结点叫做头结点,最后一个结点叫做尾结点。其中,头结点用来记录链表的基地址。有了它,我们就可以遍历得到整条链表。而尾结点特殊的地方是:指针不是指向下一个结点,而是指向一个空地址 Null,表示这是链表上最后一个结点。

与数组一样,链表也支持数据的查找、插入和删除操作。

我们知道,在进行数组的插入、删除操作时,为了保持内存数据的连续性,需要做大量的数据搬移,所以时间复杂度是 O(n)。而在链表中插入或者删除一个数据,我们并不需要为了保持内存的连续性而搬移结点,因为链表的存储空间本身就不是连续的。所以,在链表中插入和删除一个数据是非常快速的。

image

但是,有利就有弊。链表要想随机访问第 k 个元素,就没有数组那么高效了。因为链表中的数据并非连续存储的,所以无法像数组那样,根据首地址和下标,通过寻址公式就能直接计算出对应的内存地址,而是需要根据指针一个结点一个结点地依次遍历,直到找到相应的结点。

你可以把链表想象成一个队伍,队伍中的每个人都只知道自己后面的人是谁,所以当我们希望知道排在第 k 位的人是谁的时候,我们就需要从第一个人开始,一个一个地往下数。所以,链表随机访问的性能没有数组好,需要 O(n) 的时间复杂度。

循环链表

循环链表是一种特殊的单链表。。实际上,循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道,单链表的尾结点指针指向空地址,表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。从我画的循环链表图中,你应该可以看出来,它像一个环一样首尾相连,所以叫作“循环”链表。

image

双向链表

单向链表只有一个方向,结点只有一个后继指针 next 指向后面的结点。而双向链表,顾名思义,它支持两个方向,每个结点不止有一个后继指针 next 指向后面的结点,还有一个前驱指针 prev 指向前面的结点。

image

图中我们可以看到,双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以,如果存储同样多的数据,双向链表比单向链表占用更多的内存空间。虽然两个指针比较浪费存储空间,但可以支持双向遍历,这样也带来了双向链表操作的灵活性。那相比单向链表,双向链表适合解决哪种问题呢?

从结构上来看,双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点,正是这样的特点,也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

我们先来看删除操作。

在实际的软件开发中,从链表中删除一个数据无外乎两种情况:

  • 删除结点中“值等于某个给定值”的结点;
  • 删除给定指针指向的结点。

对于第一种情况,不管是单链表还是双向链表,为了查找到值等于给定值的结点,都需要从头结点开始一个一个依次遍历对比,直到找到值等于给定值的结点,然后再通过我前面讲的指针操作将其删除。

尽管单纯的删除操作时间复杂度是 O(1),但遍历查找的时间是主要的耗时点,对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则,删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。

对于第二种情况,我们已经找到了要删除的结点,但是删除某个结点 q 需要知道其前驱结点,而单链表并不支持直接获取前驱结点,所以,为了找到前驱结点,我们还是要从头结点开始遍历链表,直到 p->next=q,说明 p 是 q 的前驱结点。

但是对于双向链表来说,这种情况就比较有优势了。因为双向链表中的结点已经保存了前驱结点的指针,不需要像单链表那样遍历。所以,针对第二种情况,单链表删除操作需要 O(n) 的时间复杂度,而双向链表只需要在 O(1) 的时间复杂度内就搞定了!

同理,如果我们希望在链表的某个指定结点前面插入一个结点,双向链表比单链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定,而单向链表需要 O(n) 的时间复杂度。你可以参照我刚刚讲过的删除操作自己分析一下。

实际上,这里有一个更加重要的知识点需要你掌握,那就是用空间换时间的设计**。当内存空间充足的时候,如果我们更加追求代码的执行速度,我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反,如果内存比较紧缺,比如代码跑在手机或者单片机上,这个时候,就要反过来用时间换空间的设计思路。

还是开篇缓存的例子。缓存实际上就是利用了空间换时间的设计**。如果我们把数据存储在硬盘上,会比较节省内存,但每次查找数据都要询问一次硬盘,会比较慢。但如果我们通过缓存技术,事先将数据加载在内存中,虽然会比较耗费内存空间,但是每次数据查询的速度就大大提高了。

所以我总结一下,对于执行较慢的程序,可以通过消耗更多的内存(空间换时间)来进行优化;而消耗过多内存的程序,可以通过消耗更多的时间(时间换空间)来降低内存的消耗。你还能想到其他时间换空间或者空间换时间的例子吗?

链表 VS 数组性能大比拼

通过前面内容的学习,你应该已经知道,数组和链表是两种截然不同的内存组织方式。正是因为内存存储的区别,它们插入、删除、随机访问操作的时间复杂度正好相反。

image

不过,数组和链表的对比,并不能局限于时间复杂度。而且,在实际的软件开发中,不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。

数组简单易用,在实现上使用的是连续的内存空间,可以借助 CPU 的缓存机制,预读数组中的数据,所以访问效率更高。而链表在内存中并不是连续存储,所以对 CPU 缓存不友好,没办法有效预读。

数组的缺点是大小固定,一经声明就要占用整块连续内存空间。如果声明的数组过大,系统可能没有足够的连续内存空间分配给它,导致“内存不足(out of memory)”。如果声明的数组过小,则可能出现不够用的情况。这时只能再申请一个更大的内存空间,把原数组拷贝进去,非常费时。链表本身没有大小的限制,天然地支持动态扩容,我觉得这也是它与数组最大的区别。

解答开篇

好了,关于链表的知识我们就讲完了。我们现在回过头来看下开篇留给你的思考题。如何基于链表实现 LRU 缓存淘汰算法?

我的思路是这样的:我们维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。

  1. 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。
  2. 如果此数据没有在缓存链表中,又可以分为两种情况:
    • 如果此时缓存未满,则将此结点直接插入到链表的头部;
    • 如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。

这样我们就用链表实现了一个 LRU 缓存,是不是很简单?

现在我们来看下 m 缓存访问的时间复杂度是多少。因为不管缓存有没有满,我们都需要遍历一遍链表,所以这种基于链表的实现思路,缓存访问的时间复杂度为 O(n)。

实际上,我们可以继续优化这个实现思路,比如引入散列表(Hash table)来记录每个数据的位置,将缓存访问的时间复杂度降到 O(1)。因为要涉及我们还没有讲到的数据结构,所以这个优化方案,我现在就不详细说了,等讲到散列表的时候,我会再拿出来讲。

【基础篇】排序:归并排序

归并排序的原理

归并排序的核心**还是蛮简单的。如果想要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就有序了。

image

归并排序使用的是分治**。分治,顾名思义,就是分而治之,将一个大问题分解成小的子问题来解决。小的子问题解决了,大问题也就解决了。

从刚才的描述,可以发现分治**跟我们前面讲的递归**很像。是的,分治算法一般都是用递归来实现的。分治是一种解决问题的处理**,递归是一种编程技巧,这两者并不冲突。

实现代码如下:

function mergeSort(arr) {
    let len = arr.length;
    if(len === 1) return arr;

    let mid = Math.floor(len / 2);
    let left = arr.slice(0, mid);
    let right = arr.slice(mid, len);

    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    let result = [];
    let l = 0;
    let r = 0;

    while(l < left.length && r < right.length) {
        if(left[l] <= right[r]) {
            result.push(left[l++])
        }else{
            result.push(right[r++])
        }
    }

    while(l < left.length) {
        result.push(left[l++])
    }

    while(r < right.length) {
        result.push(right[r++])
    }

    return result;
}

归并排序的性能分析

第一,归并排序是稳定的排序算法嘛?

归并排序稳不稳定关键要看 merge 函数,也就是两个有序字数组合并成一个有序数组的那部分代码。如果有左右两个数组有相等的元素,优先把左边的元素放入数组,保证顺序不变。因此,归并排序是一个稳定的排序算法。

第二,归并排序的时间复杂度是多少?

递归的适用场景是,一个问题 a 可以分解为多个子问题 b、c,那求解问题 a 就可以分解为求解问题 b、c。问题 b、c 解决之后,我们再把 b、c 的结果合并成 a 的结果。

如果我们定义求解问题 a 的时间是 T(a),求解问题 b、c 的时间分别是 T(b) 和 T( c),那我们就可以得到这样的递推关系式:

T(a) = T(b) + T(c) + K

其中 K 等于将两个子问题 b、c 的结果合并成问题 a 的结果所消耗的时间。

从刚刚的分析,我们可以得到一个重要的结论:

不仅递归求解的问题可以写成递推公式,递归代码的时间复杂度也可以写成递推公式。

套用这个公式,我们来分析一下归并排序的时间复杂度。

我们假设对 n 个元素进行归并排序需要的时间是 T(n),那分解成两个子数组排序的时间都是 T(n/2)。我们知道,merge() 函数合并两个有序子数组的时间复杂度是 O(n)。所以,套用前面的公式,归并排序的时间复杂度的计算公式就是:

T(1) = C;   n=1 时,只需要常量级的执行时间,所以表示为 C。
T(n) = 2*T(n/2) + n; n>1

通过这个公式,如何来求解 T(n) 呢?还不够直观?那我们再进一步分解一下计算过程。

T(n) = 2*T(n/2) + n
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n
     ......

通过这样一步一步分解推导,我们可以得到 T(n) = 2^kT(n/2^k)+kn。当 T(n/2^k)=T(1) 时,也就是 n/2^k=1,我们得到 k=log2n 。我们将 k 值代入上面的公式,得到 T(n)=Cn+nlog2n 。如果我们用大 O 标记法来表示的话,T(n) 就等于 O(nlogn)。所以归并排序的时间复杂度是 O(nlogn)。

从我们的原理分析和伪代码可以看出,归并排序的执行效率与要排序的原始数组的有序程度无关,所以其时间复杂度是非常稳定的,不管是最好情况、最坏情况,还是平均情况,时间复杂度都是 O(nlogn)。

第三,归并排序的空间复杂度是多少?

归并排序的时间复杂度任何情况下都是 O(nlogn),看起来非常优秀。(待会儿你会发现,即便是快速排序,最坏情况下,时间复杂度也是 O(n2)。)但是,归并排序并没有像快排那样,应用广泛,这是为什么呢?因为它有一个致命的“弱点”,那就是归并排序不是原地排序算法。

这是因为归并排序的合并函数,在合并两个有序数组为一个有序数组时,需要借助额外的存储空间。这一点你应该很容易理解。那我现在问你,归并排序的空间复杂度到底是多少呢?是 O(n),还是 O(nlogn),应该如何分析呢?

如果我们继续按照分析递归时间复杂度的方法,通过递推公式来求解,那整个归并过程需要的空间复杂度就是 O(nlogn)。不过,类似分析时间复杂度那样来分析空间复杂度,这个思路对吗?

实际上,递归代码的空间复杂度并不能像时间复杂度那样累加。刚刚我们忘记了最重要的一点,那就是,尽管每次合并操作都需要申请额外的内存空间,但在合并完成之后,临时开辟的内存空间就被释放掉了。在任意时刻,CPU 只会有一个函数在执行,也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小,所以空间复杂度是 O(n)。

【入门篇】复杂度分析(上)

什么是算法复杂度?

我们都知道,数据结构和算法本身是为了解决“快”和“省”的问题,即如何让代码运行更快,如何让代码更省内存空间,成了衡量一个算法执行效率的两个重要标准,简称就是 时间复杂度空间复杂度

为什么需要复杂度分析?

传统的性能测试(事后统计法),就是把代码跑一遍,通过统计、监控,得到算法执行的时间和占用的内存,但是这种测试非常依赖测试坏境,并且测试结果受数据规模的影响很大。

相反,复杂度分析不依赖执行环境,就可以粗略的估算出算法的执行效率,成本小,易操作,指导性强,如果掌握了复杂度分析,往往能编写出性能更优的代码,有利于降低系统开发和维护成本。

大 O 复杂度表示法

算法的执行效率,粗略的讲,就是算法的执行时间。但是,如何在不运行代码的情况下,用“肉眼”就能看出一段代码的执行时间呢?

这里有一段非常简单的代码,求 1,2,3…n 的累加和,我们来尝试估算下该代码的执行时间。

function cal(n) {
    let sum = 0;
    let i = 1;
    for(; i <= n; i++) {
        sum += i;
    }
    return sum;
}

我们假设每行代码的执行时间都是一样的,为 unit_time,那么第 2、3 行代码分别需要 1 个 unit_time 的执行时间,第 4 、 5 行代码分别运行了 n 遍,因此需要 2n * unit_time 的执行时间,所以这段代码总的执行时间为 (2n+2) * unit_time。可以看出来,所有代码的执行时间 T(n) 与每行代码的执行次数成正比。

按照这个思路,我们再分析一段代码。

function cal(n) {
    let sum = 0;
    let i = 1;
    for(; i <= n; i++) {
        let j = 1;
        for(; j <= n; j++) {
            sum += i * j;
        }   
    }
    return sum;
}

第 2、3 行代码,每行都需要 1 个 unit_time 的执行时间,第 4、5 行代码循环执行了 n 遍,需要 2n * unit_time 的执行时间,第 6、7 行代码循环执行了 $n^{2}$ 次,所以需要 2$n^{2}$ * unit_time 的执行时间,所以,整段代码的执行时间 T(n) = (2n + 2$n^{2}$ + 2) * unit_time。

尽管我们不知道 unit_time 的具体值,但是通过这两段代码执行时间的推导过程,我们可以得到,所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比

我们把这个规律总结成一个公式,那就是 大O表示法

image

其中,T(n) 表示代码执行的时间,n 表示数据规模的大小,f(n) 表示每行代码的执行次数总和,公式中的 O,表示代码中的执行时间 T(n) 和 f(n) 成正比。

所以第一个例子中的 T(n) = O(2n + 2),第二个例子中的 T(n) = O(2n + 2$n^{2}$ + 2),就是 大O时间复杂度表示法

大O时间复杂度实际上并不代表代码真正的执行时间,而是代表代码执行时间随数据规模增长的变化趋势,简称时间复杂度

当 n 很大时,你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略。我们只需要记录一个最大量级就可以了,如果用大 O 表示法表示刚讲的那两段代码的时间复杂度,就可以记为:T(n) = O(n); T(n) = O(n)。

时间复杂度分析

1. 只关注循环次数最多的一段代码

大 O 这种复杂度表示方法只是表示一种变化趋势。我们通常会忽略掉公式中的常量、低阶、系数,只需要记录一个最大阶的量级就可以了。所以,我们在分析一个算法、一段代码的时间复杂度的时候,也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的 n 的量级,就是整段要分析代码的时间复杂度。

还是那之前的例子来说。

function cal(n) {
    let sum = 0;
    let i = 1;
    for(; i <= n; i++) {
        sum += i;
    }
    return sum;
}

其中第 2、3 行代码都是常量级的执行时间,与 n 的大小无关,所以对于复杂度并没有影响。循环执行次数最多的是第 4、5 行代码,所以这块代码要重点分析。前面我们也讲过,这两行代码被执行了 n 次,所以总的时间复杂度就是 O(n)。

2. 加法法则:总复杂度等于量级最大的那段代码的复杂度

我们先来看一段代码。

function cal(n) {
    let sum1 = 0;
    let sum2 = 0;
    let sum3 = 0;
    // 第一部分
    for(let i = 1; i <= 100; i++) {
        sum1 += i;
    }
    // 第二部分
    for(let i = i; i <= n; i++) {
        sum2 += i
    }
    // 第三部分
    for(let i = 1; i <= n; i++) {
        for(let j = 1; j <= n; j++) {
            sum3 = sum3 + i + j;
        }
    }

    return sum1 + sum2 + sum3;
}

这个代码分为三部分,分别是求 sum_1、sum_2、sum_3。我们可以分别分析每一部分的时间复杂度,然后把它们放到一块儿,再取一个量级最大的作为整段代码的复杂度。

第一段的时间复杂度是多少呢?这段代码循环执行了 100 次,所以是一个常量的执行时间,跟 n 的规模无关。

那第二段代码和第三段代码的时间复杂度是多少呢?答案是 O(n) 和 O($n^{2}$)。

综合这三段代码的时间复杂度,我们取其中最大的量级。所以,整段代码的时间复杂度就为 O($n^{2}$),也就是说,总的时间复杂度就等于量级最大的那段代码的时间复杂度,抽象成公式就是:

如果 T1(n)=O(f(n)),T2(n)=O(g(n));那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n)))=O(max(f(n), g(n))).

3. 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

我们根据加法法则来推导出乘法法则的计算公式,如果 T1(n) = O(f(n)),T2(n) = O(g(n)),那么 T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O(f(n) * g(n))。

function cal(n) {
    let sum = 0;
    for(let i = 1; i <= n; i++) {
        sum += f(i)
    }
}

function f(n) {
    let sum = 0;
    for(let i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

单独函数 cal 的时间复杂度为 T1(n) = O(n),单独函数 f 的时间复杂度为 T2(n) = O(n),所以,整个函数 cal 的时间复杂度就是,T(n) = T1(n) * T2(n) = O(n*n) = O($n^{2}$)。

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.