大 O 符号-js教程-PHP中文网

它是一种表示法，决定算法运行的速度有多快或多慢。这个速度不是由秒决定的，而是由算法的运行时间随着元素的增加而增加多少决定的。

大O是时间和大小的关系。在整篇文章中，您将看到包含这些度量的图表，并且您将在实践中更好地理解它们。我们有两种类型的复杂性（空间和时间）。

时间复杂度： 确定执行与输入大小成正比的算法所需的时间。

空间复杂度： 确定将分配多少内存来查找我们需要的项目。

为什么要研究这个？

通过它，您可以确定算法的可扩展性
大O总是处理最坏的情况，例子如下：

示例：

您有一个列表，并且想要搜索某个项目，但该项目位于列表的末尾。最坏的情况是你必须执行尽可能多的操作，直到找到你想要的数据。

执行次数

康斯坦特节奏 O(1):

无论数组大小如何，总是花费相同的时间

示例：

增加或减少

function increment(value: number){
  return ++value
}

function decrement(value: number){
  return --value
}

登录后复制

拿走一个特定的物品

const fruits = ["apple", "orange", "grape", "banana"]

function getItem(items: string[], index: number) {
  return items[index]
}

const item = getItem(fruits, 2)
console.log(`fruit: ${item}`) // "grape"

登录后复制

获取数组的第一个元素

const animes = ["one piece", "dragon ball", "naruto", "demon slayer"]

function getFirstElement(items: string[]){
 return items[0]
}

登录后复制

获取数组中的最后一项

const animes = ["one piece", "dragon ball", "naruto", "demon slayer"]

function getLastElement(items: string[]){
 return items[item.length - 1]
}

let lastElement = getLastElement(animes)
console.log(`Last Element: ${lastElement}`)

登录后复制

Big O Notations

线性时间 O(n):

执行时间与数组大小成正比
排序和二分搜索算法
仅使用一个循环进行迭代

示例：

为了找到 10 个项目的数组中最大的数字，我将滚动所有项目，直到找到它。
在最坏的情况下，最大的数字将是最后一个。

const numbers = [0, 4, 8, 2, 37, 11, 7, 48]

function getMaxValue(items: number[]) {
    let max = numbers[0];
    for (let i=0; i <= items.length; i++){
      if(items[i] > max) {
        max = items[i]
      }
    }

    return max;
}

let maxValue = getMaxValue(numbers)

console.log(`Max Value: ${maxValue}`)

登录后复制

Big O Notations

对数时间 O(log n)

输入大小增加n，执行时间增加log n，时间以对数比例增长。
记住 n 是数组中元素的数量。
输入的增长速度快于执行时间。

示例：

我们将在数组中执行二分搜索来查找特定项目。

const numbers = [0, 9, 24, 78, 54, 88, 92, 100, 21, 90]

function binarySearch(nums: number[], target: number) {
    let left = 0;
    let right = nums.length - 1;

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

        if (nums[middle] === target) {
            return middle;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }

    return -1;
}

let getTarget = binarySearch(numbers, 92)
console.log(`Target: ${getTarget}`)

登录后复制

为了更好地理解对数增长，让我们看如下：我们在示例中使用的数组有 10 个输入，因此：

log2(10) = 3.4
log2(20) = 4.3
log2(40) = 5.3

下面的图表将更容易理解：

Big O Notations

线性/拟线性时间 O(n log n)

算法的时间复杂度是指执行n次对数运算。
O(log(n)) 和 O(n) 的混合。
归并排序就是一个结构示例。
适度增长。

Big O Notations

一部分以 n 为单位，另一部分以 log(n) 为单位，下面的例子是一个幸运的合并：

function increment(value: number){
  return ++value
}

function decrement(value: number){
  return --value
}

登录后复制

二次时间 O(n²)

随着输入数量的增加，执行时间呈二次方增加。
阅读矩阵。
基本上当需要 2 个嵌套循环时
冒泡排序

Big O Notations

示例：

const fruits = ["apple", "orange", "grape", "banana"]

function getItem(items: string[], index: number) {
  return items[index]
}

const item = getItem(fruits, 2)
console.log(`fruit: ${item}`) // "grape"

登录后复制

时间指数 O(2ˆn)

每插入一个元素到输入中，执行时间就会加倍。

Big O Notations

此代码的一个示例是斐波那契

const animes = ["one piece", "dragon ball", "naruto", "demon slayer"]

function getFirstElement(items: string[]){
 return items[0]
}

登录后复制

阶乘时间 O(n!)

执行时间根据输入的大小按阶乘增加。

示例：

生成数组内的所有排列

const animes = ["one piece", "dragon ball", "naruto", "demon slayer"]

function getLastElement(items: string[]){
 return items[item.length - 1]
}

let lastElement = getLastElement(animes)
console.log(`Last Element: ${lastElement}`)

登录后复制

Big O Notations

以上是大 O 符号的详细内容。更多信息请关注PHP中文网其他相关文章！