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

开始

时间复杂度

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

    }

}

let length = arr.length

console.log(arr[i])

3. 循环条件部分，首先是 let i = 0，只会执行一次，记为 1 次
4. 然后是i < length这个判断，想要退出循环，这里最后肯定要比循环次数多判断一次，所以记为 n + 1 次
5. 最后是 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])

        }

    }

}

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

let lenOne = arr.length

2. 第一层循环，let i = 0 1次，i < lenOne n + 1 次，i++ n 次，let len_two = arr[i].length n 次
3. 第二层循环，let j = 0 n 次，j < lenTwo n * (n + 1) 次，j++ n * n 次
4. 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)

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

空间复杂度

先看看copilot的解释：

• 来一个🌰看看吧：

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

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

你学废了吗？