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

php中文网 2024-10-15 11:52:38

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

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

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

一些常见的 o 符号

o(1) – 恒定时间

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

立即学习“Java免费学习笔记（深入）”；

示例 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 



<p>在此示例中：</p>

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

示例 2：在数组中搜索值

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

function findvalue(arr, target) {
  for (let i = 0; i 



<p>在此示例中：</p>

如果数组有 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 



<p>这是发生的事情：</p>

外循环运行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 



<h3>
  
  
  运作原理：
</h3>

首先将数组的中间元素与目标进行比较。
如果中间元素是目标，则完成。
如果中间元素小于目标，则丢弃数组的左半部分并仅在右半部分搜索。
如果中间元素较大，则丢弃右半部分并在左半部分搜索。
每次，您都会将数组切成两半。

最后的话

大 o 表示法 用于描述算法的时间或空间复杂度如何随着输入大小的增长而变化。它为我们提供了一种讨论算法效率的方法，特别是当输入变大时。 big o 专注于最坏情况，帮助我们了解算法性能的上限。

以上就是DSA 与 JS：用 JavaScript 解释大 O 表示法的详细内容，更多请关注php中文网其它相关文章！

本文地址： http://www.ipsmc.com/web/10686.html