数据结构和算法：大o符号-DEV365 开发者社区

介绍

大o符号是形式上模糊计数的一种方式。
它使我们能够正式谈论随着输入的增长，算法的运行时间如何增长。
它用于分析算法的性能。

良好的性能算法是：

在大o中，我们主要集中精力：

这是计算机在执行算法期间必须执行的操作数量。无论我们使用什么计算机，这都是不变的。

function addUpTo(n){
    return n * (n + 1) / 2;
}

上述功能具有3个操作： *， +和 /输入是1还是1000000。

function addUpTo(n) {
    let total = 0;
    for(let i = 1; i <= n; i++){
        total +=1;
    }
    return total;
}

另一方面，如果您认为n为3：
（总计= 0），（让i = 1），<= n（i <= n）三次， +（i ++）三次， +=（总 += 1）三次。
现在考虑一个输入，例如n = 1000，这些输入将是for循环中的1000倍操作。

给定上面的示例，对于情况，大o表示法的方式如下：

随着输入的大小增加，算法占用的空间。

当我们谈论空间复杂性时，我们主要是指Auxiliary Space Complexity，它指的是算法所需的空间，而不包括输入占用的空间。

示例1：

function addUpTo(n) {
    let total = 0;
    for(let i = 1; i <= n; i++){
        total +=1;
    }
    return total;
}

在这里，我们有两个变量占用空间，而算法执行：total和i。不管输入的大小如何，总是使用两个空间，因此以上函数代表O(1)空间复杂性。

示例2：

function double(arr) {
    let newArr = [];
    for(let i = 0; i < arr.length; i++){
        newArr.push(2 * arr[i])
    }
    return newArr;
}

另一方面，此功能是O(n)，因为阵列长度会增长更多的空间，具体取决于输入数组中的项目。

有时大o表达式涉及更复杂的数学表达式，即对数

对数是指相位的倒数。就像划分和乘法是一对一样，这两个是。
数字的对数大约测量您可以在获得小于或等于1的值之前可以将该数字除以2的次数。

它们是无序的钥匙值对

他们在以下情况时工作良好。

这些是订购列表

他们在以下情况时工作良好。