注册

该死,这次一定要弄懂什么是时间复杂度和空间复杂度!

开始


首先,相信大家在看一些技术文章或者刷算法题的时候,总是能看到要求某某某程序(算法)的时间复杂度为O(n)或者O(1)等字样,就像这样:


image.png
Q:那么到底这个O(n)、O(1)是什么意思呢?


A:时间复杂度空间复杂度其实是对算法执行期间的性能进行衡量的依据。



Talk is cheap, show me the code!



下面从代码入手,来直观的理解一下这两个概念:


时间复杂度


先来看看copilot如何解释的


image.png



  • 举个🌰

function fn (arr) {
let length = arr.length
for (let i = 0; i < length; i++) {
console.log(arr[i])
}
}


首先来分析一下这段代码,这是一个函数,接收一个数组,然后对这个数组进行了一个遍历



  1. 第一段代码,在函数执行的时候,这段代码只会被执行1次,这里记为 1 次

let length = arr.length


  1. 循环体中的代码,循环多少次就会执行多少次,这里记为 n 次

console.log(arr[i])


  1. 循环条件部分,首先是 let i = 0,只会执行一次,记为 1 次
  2. 然后是i < length这个判断,想要退出循环,这里最后肯定要比循环次数多判断一次,所以记为 n + 1 次
  3. 最后是 i++,会执行 n

我们把总的执行次数记为T(n)


T(n) = 1 + n + 1 (n + 1) + n = 3n + 3


  • 再来一个🌰

// arr 是一个二维数组
function fn2(arr) {
let lenOne = arr.length
for(let i = 0; i < lenOne; i++) {
let lenTwo = arr[i].length
for(let j = 0; j < lenTwo; j++) {
console.log(arr[i][j])
}
}
}

来分析一下这段代码,这是一个针对二维数组进行遍历的操作,我们再来分析一下这段代码的执行次数



  1. 第一行赋值代码,只会执行1次

let lenOne = arr.length


  1. 第一层循环,let i = 0 1次,i < lenOne n + 1 次,i++ n 次,let len_two = arr[i].length n 次
  2. 第二层循环,let j = 0 n 次,j < lenTwo n * (n + 1) 次,j++ n * n 次
  3. console n*n 次

T(n) = 1 + n + 1 + n + n + n + n * (n + 1) + n * n + n * n = 3n^2 + 5n + 3

代码的执行次数,可以反映出代码的执行时间。但是如果每次我们都逐行去计算 T(n),事情会变得非常麻烦。算法的时间复杂度,它反映的不是算法的逻辑代码到底被执行了多少次,而是随着输入规模的增大,算法对应的执行总次数的一个变化趋势。我们可以尝试对 T(n) 做如下处理:



  • 若 T(n) 是常数,那么无脑简化为1
  • 若 T(n) 是多项式,比如 3n^2 + 5n + 3,我们只保留次数最高那一项,并且将其常数系数无脑改为1。

那么上面两个算法的时间复杂度可以简化为:


T(n) = 3n + 3
O(n) = n

T(n) = 3n^2 + 5n + 3
O(n) = n^2

实际推算时间复杂度时不用这么麻烦,像上面的两个函数,第一个是规模为n的数组的遍历,循环会执行n次,所以对应的时间幅度是O(n),第二个函数是 n*n的二维数组的遍历,对应的时间复杂度就是O(n^2)
依次类推,规模为n*m的二维数组的遍历,时间复杂度就是O(n*m)


常见的时间复杂度按照从小到大的顺序排列,有以下几种:


常数时间对数时间线性时间线性对数时间二次时间三次时间指数时间
O(1)O(logn)O(n)O(nlogn)O(n^2)O(n^3)O(2^n)

空间复杂度


先看看copilot的解释:


image.png



  • 来一个🌰看看吧:

function fn (arr) {
let length = arr.length
for (let i = 0; i < length; i++) {
console.log(arr[i])
}
}


在函数fn中,我们创建了变量 length arr i,函数 fn 对内存的占用量是固定的,无论,arr的length如何,所以这个函数对应的空间复杂度就是 O(1)



  • 再来一个🌰:

function fn2(n) {
let arr = []
for(let i = 0; i < n; i++) {
arr[i] = i
}
}

在这个函数中,我们创建了一个数组 arr,并在循环中向 arr 中添加了 n 个元素。因此,arr 的大小与输入 n 成正比。所以,我们说这个函数的空间复杂度是 O(n)。



  • 再再来一个🌰:

function createMatrix(n) {
let matrix = [];
for (let i = 0; i < n; i++) {
matrix[i] = [];
for (let j = 0; j < n; j++) {
matrix[i][j] = 0;
}
}
return matrix;
}

在这个函数中,我们创建了一个二维数组 matrix,并在两层循环中向 matrix 中添加了 n*n 个元素。因此,matrix 的大小与输入 n 的平方成正比。所以,我们说这个函数的空间复杂度是 O(n^2)。



  • 再再再来一个🌰:

// 二分查找算法
function binarySearch(arr, target, low, high) {
if (low > high) {
return -1;
}
let mid = Math.floor((low + high) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] > target) {
return binarySearch(arr, target, low, mid - 1);
} else {
return binarySearch(arr, target, mid + 1, high);
}
}


在二分查找中,我们每次都将问题规模减半,因此需要的额外空间与输入数据的对数成正比,我们开始时有一个大小为 n 的数组。然后,我们在每一步都将数组划分为两半,并只在其中一半中继续查找。因此,每一步都将问题的规模减半


所以,最多要划分多少次才能找到目标数据呢?答案是log2n次,但是在计算机科学中,当我们说 log n 时,底数通常默认为 2,因为许多算法(如二分查找)都涉及到将问题规模减半的操作。


2^x = n

x = log2n

常见的时间复杂度按照从小到大的顺序排列,有以下几种:


常数空间线性空间平方空间对数空间
O(1)O(n)O(n^2)O(logn)

你学废了吗?


作者:爱吃零食的猫
来源:juejin.cn/post/7320288222529536038

0 个评论

要回复文章请先登录注册