O(n*log n) 是什么？学习大 O 对数线性时间复杂度

有没有比大 O 符号更可怕的计算机科学主题？别被它的名字吓到，大 O 符号其实没什么大不了的。它很容易理解，你不需要是数学高手就能理解。在本教程中，你将通过 JavaScript 示例学习大 O 符号对数线性（或拟线性）时间复杂度的基础知识。

这是大 O 符号系列文章的第五篇。如果您想随时了解最新动态，请订阅我的每周简报“解决方案”。

Big O 解决了什么问题？

大 O 符号帮助我们回答这个问题：“它会扩展吗？”
Big O 符号为我们提供了一种与其他开发人员（和数学家！）讨论性能的共享语言。

快速复习

如果您刚刚加入我们，您将需要从那篇文章开始阅读，什么是大 O 符号？

什么是 Big O？

大 O 符号是一种用于测量算法增长率的系统。大 O 符号以数学方式描述算法在时间和空间方面的复杂度。我们不会用秒（或分钟！）来衡量算法的速度。相反，我们测量完成算法所需的操作数。

O 是“Order of”（阶数）的缩写。所以，如果我们讨论一个复杂度为 O(n^2) 的算法，我们说它的阶数（或者说增长率）是 n^2，也就是二次复杂度。

Big O 如何工作？

大 O 符号衡量最坏的情况。

为什么？

因为我们不知道我们不知道什么。

我们需要知道我们的算法表现得有多差，这样我们才能评估其他解决方案。

最坏情况也称为“上限”。我们所说的“上限”是指算法执行的最大操作数。

还记得这张桌子吗？

哦	复杂	增长率
O(1)	持续的	快速地
O（log n）	对数
在）	线性时间
O（n * log n）	对数线性
O(n^2)	二次函数
O(n^3)	立方体
O(2^n)	指数
在！）	阶乘	慢的

它按照生长速度从快到慢列出了常见的订单。

在讨论 O(n log n) 之前，让我们先回顾一下 O(n)、O(n^2) 和 O(log n)。

在）

线性时间复杂度的一个例子是简单搜索，其中根据查询检查数组中的每个元素。

const animals = [“ocelot”, “octopus”, “opossum”, “orangutan”, “orca”, “oriole”, “oryx”, “osprey”];

for (let i = 0; i < animals.length; i++) {
    if (animals[i] === userInput) {
        return `Found ${userInput} at ${i}`;
    };
};

如果您想深入了解，请查看Big O Linear Time Complexity。

O(n^2)

O(n^2) 的一个经典示例是冒泡排序。

const bubbleSort = (arr) => {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            if (arr[j] > arr[j + 1]) {
                let tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
    return arr;
};

bubbleSort()为什么是O(n^2)的阶数？

🔑 嵌套循环迭代相同的输入。

我们也可以用while循环来写这个：

const bubbleSort = arr => {

  let swapped = true;

  while (swapped) {
    swapped = false;

    for (let i = 0; i < arr.length; i++) {
      if (arr[i] > arr[i + 1]) {
        let temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        swapped = true;
      }
    }
  }
  return arr;
}

无论哪种方式，它仍然使用嵌套迭代，因此它是 O(n^2)。

如果您想深入了解，请查看Big O 二次时间复杂度。

O（log n）

二分查找是对数时间复杂度的经典例子。

const binarySearch = (arr, num) => {

   let startIndex = 0;
   let endIndex = (arr.length)-1;

   while (startIndex <= endIndex){

       let pivot = Math.floor((startIndex + endIndex)/2);

       if (arr[pivot] === num){
            return `Found ${num} at ${pivot}`;
       } else if (arr[pivot] < num){
           startIndex = pivot + 1;
       } else {
           endIndex = pivot - 1;
       }
   }
   return false;
}

🔑 每次迭代时，我们的函数都会除以输入，从而执行指数运算的逆运算。

如果您想深入了解，请查看Big O 对数时间复杂度。

O(n log n)：对数线性时间复杂度

那么 O(n log n) 是什么？

嗯，就是这样。它是线性时间复杂度n乘以对数时间复杂度log n 。

☝️

我听到你说：“先生，稍等一下。”

“您说我们要删除非主导项，那么这个n * log n是怎么回事？”

虽然我们确实会在大 O 中删除非主导项，但这通常是在我们将两个不同的复杂度相加时，例如n^2 + n。在这里，我们使用了乘法。我们无法n * log n进一步简化，因此我们保留这两个项。

O(n log n) 为我们提供了一种表示算法增长率的方法，该算法的性能优于 O(n^2)，但不如 O(n)。

计算 O(n log n)：归并排序

我们来看一个例子。O(n log n) 在排序算法中很常见（并且是理想的）。正如我们上面看到的冒泡排序，我们可以轻松地使用嵌套迭代进行强制排序，但这种方法不具备可扩展性。

这是合并排序的实现。

const nums = [128, 0, 64, 16, 4, 8, 2];

const merge = (left, right) => {

    let result = [];

    while(left.length || right.length) {

        if(left.length && right.length) {
            if(left[0] < right[0]) {
                result.push(left.shift())
            } else {
                result.push(right.shift())
            }
        } else if(left.length) {
            result.push(left.shift())
        } else {
            result.push(right.shift())
        }
    }
    return result;
};

const mergeSort = (arr) =>{
    if(arr.length <= 1) {
        return arr;
    }

    const pivot = arr.length / 2 ;
    const left = arr.slice(0, pivot);
    const right = arr.slice(pivot, arr.length);

  return merge(mergeSort(left), mergeSort(right));
};

我们以前见过这个问题或类似的问题吗？

🤔

我们的merge()函数遵循类似于上面冒泡排序的模式。它接受两个数组作为参数，并通过一系列条件语句将值从数组中移出并推送到新数组中result。

将执行多少次操作merge()？

要对数组进行排序，我们需要对每个元素进行至少一次迭代，因此我们已经处于 O(n)。

发生了什么事mergeSort()？

我们的mergeSort()函数遵循与binarySearch()上述类似的模式。我们创建一个枢轴并将输入分成两个数组。

这告诉我们什么？

O（log n）。

如果我们合并两个函数，则顺序为mergeSort()O(n log n)。

大 O 对数线性时间复杂度

在本教程中，您通过 JavaScript 中的示例学习了 Big O 对数线性时间复杂度的基础知识。

O(n log n) 可以扩展吗？

是的。

我们可以做得更好吗？

出色地...

这取决于。

许多常见排序算法的时间复杂度都达到了对数线性。但并非所有排序算法都生来平等。我们将在以后的文章中探讨这个问题。如果您想随时了解最新动态，请订阅我的每周简报“解决方案”。

文章来源：https://dev.to/nielsenjared/big-o-log-linear-time-complexity-h51