当前位置：首页 > 文章列表 > 文章 > 前端 > DSA 与 JS：用 JavaScript 解释大 O 表示法

DSA 与 JS：用 JavaScript 解释大 O 表示法

来源：dev.to 2024-09-21 12:04:01 0浏览收藏

推广推荐

免费电影APP ➜

支持 PC / 移动端，安全直达

你在学习文章相关的知识吗？本文《DSA 与 JS：用 JavaScript 解释大 O 表示法》，主要介绍的内容就涉及到，如果你想提升自己的开发能力，就不要错过这篇文章，大家要知道编程理论基础和实战操作都是不可或缺的哦！

DSA 与 JS：用 JavaScript 解释大 O 表示法

废话不多说，我们直接进入正题吧。什么是大 o 表示法以及它的用途是什么？明确的答案是 big o 表示法是一种描述算法性能如何随着输入大小的增长而变化的方法。它可以帮助您了解处理越来越大的数据量时代码的速度有多快或多慢。

简单来说，big o 会告诉您最坏的情况，即随着输入变大，代码将花费多长时间或需要多少空间。

有不同类型或种类的 big o 符号来描述算法随着输入大小的增长而表现如何。这些不同的符号代表不同的效率或性能水平。每种类型都会告诉您算法根据输入大小需要多少时间或空间。

一些常见的 o 符号

o(1) – 恒定时间

当一个操作需要相同的时间来完成时，无论输入的大小如何，它都被视为o(1)。这意味着无论您处理的数据有多大或多小，执行操作的时间都是恒定的，并且不会随着输入的增长而增加。

示例 1：访问数组元素

let numbers = [10, 20, 30, 40, 50];

// if you want to access an element at a specific index, like:
let num = numbers[2]; // this will give you 30

无论数组有多大，此操作将始终花费相同的时间。无论数组有 5 个元素还是 500 万个元素，直接访问 numbers[2] 的时间总是o(1)，因为您只是使用其索引获取一个值。

示例 2：赋值

let a = 10;

示例 3：检查数字是否为偶数

function iseven(number) {
  return number % 2 === 0;
}

无论数字有多大，该函数的运行时间都是相同的。所以，这也是 o(1).

o(n) – 线性时间

在o(n)中，完成操作所需的时间随着输入的大小直接增加。如果输入加倍，执行操作所需的时间也会加倍。发生这种情况是因为算法需要处理输入中的每一项逐一。

示例 1：循环数组

假设您有一个数组，并且想要打印其中的每个元素。所需的时间取决于数组中有多少元素。这是一个简单的例子：

let numbers = [10, 20, 30, 40, 50];

for (let i = 0; i < numbers.length; i++) {
  console.log(numbers[i]);
}

在此示例中：

如果数组有 5 个元素，则循环将运行 5 次。
如果数组有 100 个元素，则循环将运行 100 次。
如果数组有 n 个元素，则循环将运行 n 次。

示例 2：在数组中搜索值

假设你想查找数组中是否存在特定值：

function findvalue(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return true;
    }
  }
  return false;
}

在此示例中：

如果数组有 10 个元素，循环可能会运行最多 10 次来查找值。
如果数组有 1,000 个元素，则循环可能最多运行 1,000 次。
对于 n 个元素，在最坏的情况下循环可能会运行 n 次。

因此，数组越大，检查每个元素所需的时间就越长，使其o(n)。

o(n²) – 二次时间

o(n²) 表示完成算法所需的时间随着输入大小的增加呈指数级增加。具体来说，如果输入大小加倍，则所需时间会增加四倍（因为 2² = 4）。如果输入增加三倍，时间就会增加九倍（因为 3² = 9）。

当您有嵌套循环时，通常会发生这种情况，其中一个循环迭代输入，然后在该循环内，另一个循环也迭代相同的输入。

数组上的嵌套循环： 假设您有一个数组，并且您想要将每个元素与数组中的每个其他元素进行比较。这是一个例子：

let numbers = [10, 20, 30, 40, 50];

for (let i = 0; i < numbers.length; i++) {
  for (let j = 0; j < numbers.length; j++) {
    console.log(numbers[i], numbers[j]);
  }
}

这是发生的事情：

外循环运行n次（其中n是数组的长度）。
对于外循环的每次迭代，内循环也运行n次。
因此，对于数组中的每个项目，您都会再次循环遍历每个项目。如果数组有 5 个元素，则 5 次外循环迭代中的每一次内循环都会运行 5 次，使其总共运行 25 次 (5 × 5 = 25)。

这使得时间复杂度 o(n²)，因为对于 n 个元素，您正在执行 n × n 操作。

o(n²) 总结： 当您有嵌套循环时，就会发生 o(n²)，其中两个循环都迭代相同的输入。所花费的时间随着输入的大小呈二次方增长。与 o(n) 和 o(log n) 相比，它的速度较慢，因为随着输入大小的增加，操作数量增长得更快。

二次时间在冒泡排序等算法或需要比较数据集中每对项目的问题中很常见。

o(log n) – 对数时间

我认为这个需要更多的关注和仔细来掌握这个概念。

在 o(log n) 中，时间随着输入大小的增大而增加，但与其他时间复杂度（如 o( n) 或 o(n²).

这里是关键思想： 在 o(log n) 算法中，每一步都会显着减少问题大小（通常减少一半），这意味着随着输入变大，所需的额外步骤数量不会增加太多。事实上，它对数增长，意味着增长非常缓慢。

比较 o(n) 和 o(log n)

o(n) – 线性时间：

如果您有 10 件商品，则可能需要 10 个步骤。
如果您有 100 个项目，则需要 100 个步骤。
如果您有 1,000 个项目，则需要 1,000 个步骤。

这里，时间随着输入大小直接增长。

o(log n) – 对数时间：

如果您有 10 个项目，则可能需要大约 4 个步骤（因为 log 2(10) ≈ 4）。
如果您有 100 个项目，则只需要大约 7 个步骤（因为 log 2(100) ≈ 7）。
如果您有 1,000 个项目，则只需要大约 10 个步骤（因为 log2(1,000) ≈ 10）。

尽管输入增长很多（从 10 到 1,000），步数（“时间”）仅略有增加（从 4 步到 10 步）。

二分查找

o(log n) 的一个经典示例是 二分搜索。假设您有一个已排序的数组，并且您想要查找数组中是否存在目标数字。您可以在每一步将搜索空间减半，而不是一一检查每个数字（这将是 o(n)）。

这是二分搜索的示例：

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1; // Search the right half
    } else {
      right = mid - 1; // Search the left half
    }
  }

  return -1; // Target not found
}