适合初学者的大 O 符号！！

为什么初学者不应该害怕 AL

作为一名代码新手，我读过一些帖子，说算法对前端开发者或 Web 开发新手来说没什么用。有一段时间，我对此不以为然，认为这是一个只有高级工程师和初学者才应该尝试的难题。但事实上，学习 AL 可以帮助你编写更好的代码，并轻松识别导致程序运行缓慢的原因。

我花了几天时间学习它，我可以说，只要你掌握了任何编程语言的语法和基础知识，你就可以开始学习算法。你不需要编程多年，你可以边学边学。越早开始越好，而且你不必是数学天才。

所以，对于所有代码新手来说，不要害怕学习，勇敢尝试，即使失败了，也要再试一次。如果你从未尝试过，就不可能擅长某件事。至于我，我曾经失败过，也解决了一些遇到的问题，但我从中吸取了教训，并且不断成长。我解决问题的能力也越来越强💪🏾。是的，我们都是学习者，在这个领域，学习永无止境。

动图

什么是算法？

这是解决问题的步骤。我们识别模式，创建能够提高程序速度的解决方案。提升性能不仅关乎编写有效的代码，也关乎算法本身。

什么是大 O 符号

大 O 符号用于解释算法的性能或复杂性。
我们也可以说，它展示了算法的运行时间如何随着输入的增长而增长。例如，如果你在一家处理大量用户数据的大公司工作，你正在编写一个高效的算法，使其运行时耗时比另一个耗时更长。

为什么大 O 符号很重要

• 它帮助我们了解算法的最坏情况。
• 描述执行时间，称为时间复杂度
• 描述所使用的空间（内存）。这称为空间复杂度。

常见的时间复杂度

1）O（n）-线性运行时间

随着函数输入的增加，运行时间也会增加。
我们来看下面的例子。

function logUpTo(n) {
    for (var i = 1; i <= n; i++) {
        console.log(i);
    }
}

在上面的函数中，我们不太关心输入 (n) 是 5 还是 1000。我们想要的是数量级（大 O），即 O(n)- ( f(n) = n )。随着输入大小的增加，循环运行所需的时间也会增加。

2）O（n^2）二次运行时间

运行时间与输入的平方（n^2）成正比。因此，随着输入的增长，运行时间也会增长 n * n 。
为了更好地理解，我们来看下面的例子。

const pairs = (n)=> {
    for (var i = 0; i < n; i++) {
      for (var j = 0; j < n; j++) {
        console.log(i, j);
      }
    }
}
pairs(2);
/*
output
0 0 
0 1
1 0 
1 1
*/

上面的函数有一个嵌套循环。当 n 增加时，第一个循环的运行次数会增加，第二个循环的运行次数也会增加。这就是 = ( f(n) = n ^ 2 )

O(1) 恒定运行时

随着函数输入的增加，运行时间不会改变，它保持不变。
让我们看下面的例子。

function logAtMost10(n) {
    for (var i = 1; i <= Math.min(n, 10); i++) {
        console.log(i);
    }
}

上面的函数中，当输入大于 10 时，返回 1-10。即使输入为 1M，输出仍然是 1-10。随着 n 的增加，函数的运行时间保持不变，即 f(n) = 1。

在大 O 符号中，较小的项并不重要。例如：

O(n + 50) => O(n) '

如果去掉 50，则时间为 O(n)

O(8000n + 50) => O(n)

O(n^2 + 10n + 3) => O(n * n)/ O(n2)

从更大的范围来看，5n + 6 并不重要，但 n^2 很重要。

O(n^2 + n^3) => O(n^3)

需要注意的几点

算术运算（+、-、/、*）是常量。

如果你进行加、减或乘法运算，所需的运行时间是相同的，因此是常数。
当你在计算机上执行 1 + 1 和 3 + 1000000000 时，执行这些运算所需的时间大致相同。

赋值变量是常量。

将变量 x 分配给 10 所花费的时间与将变量 y 分配给 1,000,000 所花费的时间相同。

辅助空间

辅助空间是指运行算法所需的内存或空间量。但随着空间复杂度的提高，所需的空间总量会随着输入规模的增加而增长。

让我们看一些例子。

问题 1

//O(1)
const total= (n) => {
    let total = 0;
    for (let i = 0; i < n.length; i++) {
        total += n[i];
    }
    return total;
}

O(1) 空间 - 这意味着无论输入如何，空间都是相同的。因此输入的增加或减少不会影响空间。

问题 2

const double = (n) => {
    let total = [];
    for(let i = 0; i < n.length; i++) {
        total.push(2 * n[i]);
    }
    return total; // return n numbers
    //O(n) space
}

在上面的函数中，如果输入有 10 个元素，则创建的新数组将包含 10 个元素，且元素数量翻倍。所需空间为 O(n)。

包含所有运行时复杂性的简单表格

练习用的问题。

以下问题的时间复杂度和辅助空间是多少
问题1

function subtotals(array) {
    var subtotalArray = Array(array.length);
    for (var i = 0; i < array.length; i++) {
        var subtotal = 0;
        for (var j = 0; j <= i; j++) {
            subtotal += array[j];
        }
        subtotalArray[i] = subtotal;
    }
    return subtotalArray;
}

问题 2

function onlyElementsAtEvenIndex(array) {
    var newArray = Array(Math.ceil(array.length / 2));
    for (var i = 0; i < array.length; i++) {
        if (i % 2 === 0) {
            newArray[i / 2] = array[i];
        }
    }
    return newArray;

}

问题 3

function logAtMost10(n) {
    for (var i = 1; i <= Math.max(n, 10); i++) {
        console.log(i);
    }
}

结论：
以上就是我目前学到的知识，希望对您有所帮助。随着我继续学习算法，我会陆续更新。
感谢你阅读了所有内容。

一些资源

• 前端大师的 JavaScript 算法实用指南
• YK Sugishita (CS Dojo) Youtube 频道的算法
• 大 O 符号初学者指南

如果这篇文章对你有帮助，你也可以支持我。🙂