大 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中文網其他相關文章！