8月阅读周·秒懂算法:用常识解读数据结构与算法:使用大O给代码提速
【摘要】 背景去年下半年,我在微信书架里加入了许多技术书籍,各种类别的都有,断断续续的读了一部分。没有计划的阅读,收效甚微。新年伊始,我准备尝试一下其他方式,比如阅读周。每月抽出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)