8月阅读周·秒懂算法:用常识解读数据结构与算法:使用大O给代码提速

举报
叶一一 发表于 2024/08/26 14:09:45 2024/08/26
339 0 0
【摘要】 背景去年下半年,我在微信书架里加入了许多技术书籍,各种类别的都有,断断续续的读了一部分。没有计划的阅读,收效甚微。新年伊始,我准备尝试一下其他方式,比如阅读周。每月抽出1~2个非连续周,完整阅读一本书籍。这个“玩法”虽然常见且板正,但是有效,已经坚持阅读七个月。已读完书籍:《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript(上卷)》、《你不知道的JavaScri...

背景

去年下半年,我在微信书架里加入了许多技术书籍,各种类别的都有,断断续续的读了一部分。

没有计划的阅读,收效甚微。

新年伊始,我准备尝试一下其他方式,比如阅读周。每月抽出1~2个非连续周,完整阅读一本书籍。

这个“玩法”虽然常见且板正,但是有效,已经坚持阅读七个月。

已读完书籍《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript(上卷)》、《你不知道的JavaScript(中卷)》、《你不知道的JavaScript(下卷)》、《数据结构与算法JavaScript描述》、《WebKit技术内幕》、《前端架构:从入门到微前端》

当前阅读周书籍《秒懂算法:用常识解读数据结构与算法》

使用大O给代码提速

大O记法是表达算法效率的绝佳工具。我们使用它量化了二分查找与线性查找的效率差别——二分查找是O(log N)算法,比O(N)的线性查找快得多。

冒泡排序

已知一个无序数组,如何排序才能使其中的值按升序排列?最初的几个容易理解、效率一般,因此也被称为“简单排序”。

冒泡排序是一种基本排序算法,其步骤如下:

步骤1:指向数组中两个连续的值。(从前两个值开始。)比较它们的值。

步骤2:如果这两个值顺序错误(也就是左边的值大于右边的值),那么就交换它们的位置(如果它们的顺序正确,那么这一步就什么都不做。

步骤3:把“指针”右移一个格子。

步骤4: 重复步骤1~3,直到抵达数组末尾或者遇到已经排好序的值。(等后面详细分析时你就明白了。)至此,我们已经完成了数组的第一次遍历。换言之,我们已经指向过数组的每一个值,并抵达了数组末尾。

步骤5:把两个指针移动回数组开头,重复步骤1~4,再次遍历数组。不断遍历数组,直到无须交换任何值。至此,数组排序完毕。

冒泡排序的效率

冒泡排序有两类重要步骤。

  • 比较:比较两个数的大小。
  • 交换:交换顺序错误的数。

先来确定冒泡排序所需的比较次数。

例子中的数组有5个元素。回顾第一次遍历,可以知道我们做了4次两两比较。

第二次遍历只需要3次比较。因为第一次遍历之后,最后一个数的位置正确,所以无须比较最后两个数。

第三次遍历需要2次比较,而第四次遍历只需要1次比较。

所以总计需要4 + 3 + 2 + 1 = 10次比较。

为了覆盖大小不一的各种数组,我们会说对于N个元素,需要(N - 1) + (N - 2) + (N -3) + … + 1次比较。

在分析完冒泡排序需要的比较次数后,下面来分析交换。

在最坏的情况下,数组按降序排列(和我们的目标正相反),每次比较都需要交换。因此,这种情况需要10次比较和10次交换,共计20步。

因为冒泡排序处理N个值需要N2步,所以它的效率是O(N^2)。

O(N^2)是一个效率相对较低的算法。随着数据量的增加,步骤数会急剧增加。下图对O(N^2)和更快的O(N)进行了比较。

O(N^2)的曲线随着数据量增长快速上扬。而O(N)只是一条简单的斜线。

平方问题

在下面的实例中,可以用O(N)算法来代替较慢的O(N2)算法。

假设你要开发一个JavaScript应用,分析人们对产品的评分,分数的范围是1到10。在应用中,你需要写一个函数,该函数用于检查评分数组是否有重复分数。软件中的其他复杂计算会调用这个函数。

例如,数组[1, 5, 3, 9, 1, 4]中有两个1,因此函数需要返回true,表示该数组存在重复分数。

你首先想到的方法可能是用下面这个嵌套循环:

function hasDuplicateValue(array) {
    for(let i = 0; i < array.length; i++) {
        for(let j = 0; j < array.length; j++) {
            if(i !== j && array[i] === array[j]) {
                return true;
            }
        }
    }
    return false;
}

在这个函数中,先用变量i遍历数组中的每个值。对于每个i表示的值,用变量j在另一个循环中再次遍历数组的所有值,检查索引i和j处的值是否相同。如果相同,那么数组中就存在重复,函数会返回true。如果循环结束后没有发现任何重复,那么数组中就不含重复分数,函数会返回false。

这个算法是正确的,但是它的效率如何呢?既然我们已经学习了大O记法,那么不如来看看该算法的时间复杂度是什么。

上面的函数只有一类步骤,也就是比较。它不断比较array[i]和array[j],检查它们是否相等,也就是是否存在重复。在最坏情况下,数组不含重复数字,代码必须运行所有循环,进行所有比较才能返回false。

因此,对于有N个值的数组,函数需要执行N^2次比较。这是因为外层循环必须执行N次才能遍历整个数组,而在每次循环中,内层循环也要执行N次。总共需要N × N,也就是N^2步,因此算法的复杂度是O(N^2)。

通过向函数中添加记录算法步骤数的代码,可以证明函数确实执行了N^2步。

function hasDuplicateValue(array) {
    let steps = 0; // 步骤数
    for(let i = 0; i < array.length; i++) {
        for(let j = 0; j < array.length; j++) {
            steps++; // 步骤数加1
            if(i !== j && array[i] === array[j]) {
                return true;
            }
        }
    }
    console.log(steps); // 如果不含重复数字,那么就打印步骤数
    return false;
}

添加的代码会在不含重复数字时打印所需步骤数。如果运行hasDuplicateValue([1, 4,5, 2, 9]),那么就会在JavaScript控制台中看到25。这意味着对于这个有5个元素的数组,一共执行了25次比较。如果用其他数组来测试,则会发现输出总是数组大小的平方。这是经典的O(N^2)算法。

总结

深刻理解大O记法,能让你找出运行缓慢的代码,并且在两个算法中选择最优解。

不过,有时两个算法的时间复杂度一致,速度却不一样。如何在大O记法无法判断的时候评估不同算法的效率?我们下篇揭晓答案。


作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者,刑侦、无限流小说初级玩家。
如果看完文章有所收获,欢迎点赞👍 | 收藏️ | 留言📝

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

作者其他文章

评论(0

抱歉,系统识别当前为高风险访问,暂不支持该操作

    全部回复

    上滑加载中

    设置昵称

    在此一键设置昵称,即可参与社区互动!

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。