Notasi O Besar

Ia adalah tatatanda yang menentukan kelajuan atau perlahan algoritma berjalan. Kelajuan ini tidak ditentukan oleh saat, tetapi oleh berapa banyak masa berjalan algoritma meningkat apabila elemen meningkat.

Big O ialah hubungan antara masa dan saiz. Sepanjang artikel, anda akan melihat graf dengan langkah ini dan anda akan memahaminya dengan lebih baik dalam amalan. Kami mempunyai dua jenis kerumitan (ruang dan temporal).

Kerumitan Tempoh: Menentukan tempoh masa yang diperlukan untuk melaksanakan algoritma yang berkadar dengan saiz input.

Kerumitan Spatial: Menentukan jumlah memori yang akan diperuntukkan untuk mencari item yang kita perlukan.

Mengapa mengkaji ini?

• Dengan ini anda boleh menentukan sejauh mana algoritma boleh berskala
• Big O sentiasa berurusan dengan kes terburuk, contoh di bawah:

contoh:

• Anda mempunyai senarai dan anda ingin mencari item tetapi item itu berada di hujung senarai. Senario kes terburuk ialah anda perlu melakukan sebanyak mungkin operasi sehingga anda menemui data yang anda mahukan.

Masa pelaksanaan

Tempo Constante O(1):

• tidak kira saiz tatasusunan, ia akan sentiasa mengambil masa yang sama

contoh:

• Kenaikan atau pengurangan

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

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

• Ambil item tertentu

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"

• Dapatkan elemen pertama tatasusunan

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

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

• Dapatkan item terakhir dalam tatasusunan

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}`)

Masa Linear O(n):

• Masa pelaksanaan bertambah berkadar dengan saiz tatasusunan
• Isih dan algoritma carian binari
• lelaran menggunakan hanya satu gelung

contoh:

• Untuk mencari nombor terbesar dalam susunan 10 item, saya akan menatal semua item sehingga saya menemuinya.
• Dalam kes yang paling teruk, bilangan terbesar akan menjadi yang terakhir.

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}`)

Masa Logaritma O(log n)

• Saiz input meningkat sebanyak n dan masa pelaksanaan meningkat dengan log n, masa berkembang dalam perkadaran logaritma.
• Ingat bahawa n ialah bilangan elemen dalam tatasusunan.
• Input berkembang lebih cepat daripada masa pelaksanaan.

contoh:

• kami akan melakukan carian binari dalam tatasusunan untuk mencari item tertentu.

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}`)

• Untuk lebih memahami pertumbuhan logaritma, mari kita lihat seperti berikut: tatasusunan yang kita gunakan dalam contoh mempunyai 10 input, jadi:

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

• Graf di bawah akan memudahkan pemahaman:

Masa linearitma/kuasilinear O(n log n)

• Kerumitan masa algoritma yang merujuk kepada pelaksanaan operasi logaritma n kali.
• Campuran O(log(n)) dan O(n).
• Contoh struktur ialah Isih Gabung.
• berkembang sederhana.

• Satu bahagian skala dalam n dan bahagian lain skala dalam log(n), contoh di bawah ialah gabungan bertuah:

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

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

Masa Kuadratik O(n²)

• Masa pelaksanaan meningkat secara kuadratik apabila bilangan input bertambah.
• Matriks bacaan.
• Pada asasnya apabila 2 gelung bersarang diperlukan
• Isih Buih

contoh:

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"

Eksponen Masa O(2ˆn)

• Dengan setiap elemen dimasukkan ke dalam input, masa pelaksanaan akan berganda.

• contoh kod ini ialah fibonacci

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

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

Masa Faktorial O(n!)

• Masa pelaksanaan meningkat secara berfaktor mengikut saiz input.

contoh:

• Janakan semua pilih atur dalam tatasusunan

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}`)

Atas ialah kandungan terperinci Notasi O Besar. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!