前端视角如何理解“时间复杂度O(n)”

定义

时间复杂度是O(n) 意味着算法的执行时间与输入数据的大小成正比。
这里的n表示输入数据的数量。

假设有一个数组，需要遍历这个数组并打印出每个元素的值。
这个操作的时间复杂度就是O(n)，因为你需要执行n次操作，其中n是数组的长度。

function printArrayElements(array) {
    for (let i = 0; i < array.length; i++) {
        console.log(array[i]);
    }
}
1
2
3
4
5

在这个例子中，随着数组长度的增加，需要执行的打印操作也会成比例增加。
因此，这个算法的时间复杂度是线性的，即O(n)。

简而言之，时间复杂度是O(n)意味着算法的执行时间会随着输入数据量的增加而线性增加。

---

时间复杂度为O(n)的例子

例子 1：寻找数组中的最大元素

假设我们有一个包含n个元素的数组，我们想找到其中的最大元素。
一种简单的方法是遍历整个数组并记录遇到的最大元素：

function findMaxElement(array) {
    let maxElement = array[0];
    for (let i = 1; i < array.length; i++) {
        if (array[i] > maxElement) {
            maxElement = array[i];
        }
    }
    return maxElement;
}
1
2
3
4
5
6
7
8
9

在这个例子中，我们需要检查数组中的每个元素以确定最大值，因此时间复杂度为O(n)。

例子 2：计算数组元素的和

假设我们有一个包含n个元素的数组，我们想计算所有元素的总和。我们可以通过遍历数组并累加每个元素来实现：

function sumArrayElements(array) {
    let sum = 0;
    for (let i = 0; i < array.length; i++) {
        sum += array[i];
    }
    return sum;
}
1
2
3
4
5
6
7

在这个例子中，我们需要对数组中的每个元素进行一次加法操作，因此时间复杂度同样为O(n)。

例子 3：检查数组是否包含特定元素

假设我们有一个包含n个元素的数组，我们想检查数组中是否包含一个特定的元素。我们可以通过遍历数组并比较每个元素来实现：

function containsElement(array, targetElement) {
    for (let i = 0; i < array.length; i++) {
        if (array[i] === targetElement) {
            return true;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8

在这个例子中，最坏情况下（即目标元素不存在于数组中），我们需要检查数组中的每个元素，因此时间复杂度为O(n)。

例子 4：反转数组

假设我们有一个包含n个元素的数组，我们想将其反转，即第一个元素成为最后一个元素，最后一个元素成为第一个元素，依此类推。我们可以通过交换数组的首尾元素来实现：

function reverseArray(array) {
    let left = 0;
    let right = array.length - 1;
    while (left < right) {
        let temp = array[left];
        array[left] = array[right];
        array[right] = temp;
        left++;
        right--;
    }
}

// Usage
const myArray = [1, 2, 3, 4, 5];
reverseArray(myArray);
console.log(myArray); // Output: [5, 4, 3, 2, 1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

在这个例子中，我们需要遍历数组的一半进行元素交换，因此时间复杂度仍然为O(n)。