第一模块:
课程名称:2周刷完100道前端优质面试真题
课程章节:第二章第三节
主讲老师:双越
第二模块:
课程内容概述
一. 什么是复杂度?
程序执行时需要的计算量和内存空间(和代码是否简洁无关).
复杂度是数量级(方便记忆/推广),不是具体的数字
一般是针对一个具体的算法,而非一个完整的系统.
表格如下:
O(1): 一次就够(数量级)
O(n): 和传输的数据量一样(数量级)
O(n^2):数据量的平方(数量级)
O(logn): 数据量的对数(数量级)
O(n*logn): 数据量*数据量的对数(数量级)
代码演示:
O(1):
function fn(obj={}){
return obj.a+obj.b+obj.c;
}O(n):
function fn(arr=[]){
for(let i=0;i<arr.length;i++){
console.info(arr[i]);
}
}O(n^2):
function fn(arr=[]){
for(let i=0;i<arr.length;i++){
for(let j=0;j<arr.length;j++){
console.info(arr[j]);
}
}
}二.空间复杂度
概念:程序运行时需要的内存空间
O(1):有限,可数的空间(数量级)
O(n):和输入的数据量相同的空间(数量级)
其他的不常见,只做这2个的拓展
O(1): const a = arr[1]
O(n):
const arr2 = [];
for(let i=0;i<arr.length;i++){
arr2[i] = arr[i]+10;
......
}程序员必须掌握算法复杂度
如果达到O(n^2),算法基本不可用级别
重点:
算法复杂度是学习算法的基础,非常重要,不理解就先背诵
复杂度是数量级,用O(...)表示,内部是一个函数表达式
前端开发:重时间 轻空间
第三模块:
如果你没有复杂度的概念和敏感度,写程序是非常危险的
例如,代码工程测试正常,蛋数量大了,程序就会崩溃
对于前端开发,尤其是时间复杂度
第四模块: