通过通过js示例讲解时间复杂度与空间复杂度示例讲解时间复杂度与空间复杂度
1. 博客背景博客背景
今天有同事在检查代码的时候,由于函数写的性能不是很好,被打回去重构了,细思极恐,今天和大家分享一篇用js讲解的时
间复杂度和空间复杂度的博客
2. 复杂度的表示方式复杂度的表示方式
之前有看过的,你可能会看到这么一串东西
T(n) = O(f(n))
S(n) = O(f(n))
这个叫做大O表示法,其中的T代表的是算法需要执行的总时间
S表示的算法需要的总空间
f(n)表示的是代码执行的总次数
举个例子
function go(n) {
var item = 0; // 这里执行了一次
for (var i = 0; i < n; i++) { //这里执行了N次
for (var j = 0; j < n; j++) { //这里执行了n*n次
item = item + i + j; //这里执行了n*n次
}
}
return item; //这里执行了一次
}
所以说上边这段代码是 1+n+n*n*2+1=2+n+2n²
也就是说 T(n) = O(f(2+n+2n²))
然后之前说了时间复杂度看的是一个代码执行的时间的趋势, 所以说在N,也就是规模比较大的时候,那些常量是起不到决定
性的作用的,所以这个时候我们忽略这些常量,这里的例子是一个单段的代码,这里只看最大量级的循环就可以了
所以最后的这个代码的时间复杂度是T(n) = O(n²)
大家可以想想一下数据中平方的曲线图
3. 时间复杂度时间复杂度
3.1 时间复杂度的定义时间复杂度的定义
首先什么是时间复杂度,时间复杂度这个定义如果在之前没有接触过的话,你可能会认为他代表的是一个代码执行的时间,其
实不然,算法的时间复杂度就是说一个算法的执行时间根据数据规模增长的一个趋势,并不是说代码执行的具体时间
3.2 几种常见的时间复杂度几种常见的时间复杂度
最简单的O(n)
for (var i = 0; i < n; i++) {
sum += i;
}
通俗易懂,这段代码的执行时间完全由N来控制,所以说T(n) = O(n)
当然还有个更简单的O(1)
function total(n) {
console.log(1)
}
无论怎么样,这段函数不受任何参数影响,代码走一遍就完事,这种的代码用T(n) = O(1) 表示
T(n) = O(n²)