非计算机科学学位的 Big-O 课程 - 第一部分

有没有想过为什么有些算法比其他算法更快？我也是，但大O符号很可能能解释这一点。在这个由两部分组成的系列文章中，你将了解其中的原因！

那么 Big-O 符号到底是什么？

它是一种衡量算法执行时间以及算法根据数据集大小的扩展能力的方法。本质上，它衡量的是算法的效率。

举例来说，假设我们有一个包含 15 个人的列表，我们想对这 15 个人进行排序，找出名字以字母 T 开头的每个人。那么，您可以使用不同的算法来对这个列表进行排序，这些算法的复杂程度各不相同，但有些算法的表现要优于其他算法。

现在假设列表突然增加到 100 万个名字。您认为这会对性能和复杂性产生什么影响？

可以使用 Big-O 符号找到这些问题的答案。

多种口味

Big-O 有不同的形式：
- O(1)
- O(log n)
- O(n)
- O(n log n)
- O(n^2)
- O(2^n)
- O(n!)
在这篇文章中，我将讨论前三种变体，并在下一篇文章中讨论后四种变体，敬请关注！

O（1）-恒定时间

恒定时间复杂度与传入数据的大小无关。无论数据集如何，执行时间都保持不变。无论我们的列表包含 5 个项目还是 1,000 个项目，都无关紧要。这意味着这种表示法具有极强的可扩展性，并且与时间无关。

假设我们有一个数字数组，我们想在其中找到第二个数字。无论列表的大小如何，查找第二个数字所花费的时间总是相同的。

let smallList = [0, 1, 2]

let largeList = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

let logSecondNumber = (list) => {
    console.log(list[1]);
}

logSecondNumber(smallList)
logSecondNumber(largeList)

即使一个列表比另一个列表大，对该函数的两个调用也将在相同的时间内执行。

O（log n）——对数时间

对数时间复杂度是指执行时间与输入大小的对数成正比。二分查找就是一个很好的例子。你需要不断划分数据集，直到达到你想要的点。

在下面的例子中，我循环遍历数字列表，并检查数组中的中间位置是否等于目标值。如果不相等，我们就相应地划分数字列表，计算新的中间位置，然后再次检查。这个过程会一直持续，直到找到我们要找的数字，或者数组中的数字用完为止。

function binarySearch(array, targetValue) {
    let minIndex = 0;
    let maxIndex = array.length - 1;
    let middleIndex = Math.floor((maxIndex + minIndex) / 2);

    while (array[middleIndex] != targetValue && minIndex < maxIndex) {

        if (targetValue < array[middleIndex]) {
            maxIndex = middleIndex - 1;
        } else if (targetValue > array[middleIndex]) {
            minIndex = middleIndex + 1;
        } 
        middleIndex = Math.floor((maxIndex + minIndex)/2);

    }

    return (array[middleIndex] != targetValue) ? -1 : middleIndex;
};

let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

binarySearch(numbers, 7);

O（n）-线性时间

线性时间复杂度意味着执行算法的时间与 n 的大小直接相关。随着更多项目添加到数据集中，执行时间将按比例增加。

看下面的例子，我们使用 for 循环打印出数组中的每个项。每向数组添加一个项，执行时间就会增加 n。

let junkFood = ['pizza', 'cookie', 'candy', 'icecream']

loopThroughOurJunkFood(junkFood) {
    for (let i = 0; i > junkFood.length; i++) {
    console.log(junkFood[i]);
    }
}

如果我们向 junkFood 数组中添加另一个项目，则执行函数所需的时间将线性增加。

更多内容即将推出……

在本系列的下一篇文章中，我们将介绍其余的 Big-O 符号风格，敬请关注！

如果您喜欢所看到的内容并想了解更多，请访问我的博客，我在那里撰写了更多有关软件开发以及个人发展的文章！

如果您发现这篇文章有帮助，请订阅我的时事通讯，我会每周将更多类似的内容直接发送到您的收件箱！