Notasi Big O untuk Pemula: Panduan Praktikal

Pernah terfikir mengapa sesetengah kod berjalan dengan sangat pantas manakala kod lain merangkak? Masukkan Notasi Big O - bahasa rahsia yang digunakan pembangun untuk membincangkan kecekapan algoritma. Mari kita pecahkan secara ringkas.

Apakah Notasi Big O?

Notasi Big O menerangkan cara skala prestasi kod anda apabila saiz input berkembang. Anggap ia sebagai mengukur berapa lama kod anda mengambil masa apabila anda memberikan lebih banyak kerja untuk dilakukan.

Kerumitan O Besar Biasa

O(1) - Masa Malar

Cawan suci persembahan. Tidak kira berapa besar input anda, operasi mengambil masa yang sama.

function getFirstElement(array) {
    return array[0];  // Always one operation
}

O(log n) - Masa Logaritma

Biasanya dilihat dalam algoritma yang membahagikan masalah kepada separuh setiap kali. Carian binari ialah contoh klasik.

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

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

        if (sortedArray[mid] === target) return mid;
        if (sortedArray[mid] < target) left = mid + 1;
        else right = mid - 1;
    }

    return -1;
}

O(n) - Masa Linear

Skala prestasi secara linear dengan saiz input. Biasa dalam algoritma yang perlu melihat setiap elemen sekali.

function findMax(array) {
    let max = array[0];
    for (let i = 1; i < array.length; i++) {
        if (array[i] > max) max = array[i];
    }
    return max;
}

O(n log n) - Masa Linearitma

Sering dilihat dalam algoritma pengisihan yang cekap seperti mergesort dan quicksort.

function mergeSort(array) {
    if (array.length <= 1) return array;

    const mid = Math.floor(array.length / 2);
    const left = mergeSort(array.slice(0, mid));
    const right = mergeSort(array.slice(mid));

    return merge(left, right);
}

O(n²) - Masa Kuadratik

Biasa dalam gelung bersarang. Prestasi merosot dengan cepat apabila saiz input bertambah.

function bubbleSort(array) {
    for (let i = 0; i < array.length; i++) {
        for (let j = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                [array[j], array[j + 1]] = [array[j + 1], array[j]];
            }
        }
    }
    return array;
}

Petua Praktikal untuk Menulis Kod Cekap

1. Elakkan Gelung Bersarang Apabila Boleh

   • Gunakan jadual cincang untuk carian dan bukannya lelaran bersarang
   • Pertimbangkan sama ada masalah anda boleh diselesaikan dengan menyusun dahulu

2. Pilih Struktur Data yang Sesuai

   • Susun atur untuk data tersusun dengan akses pantas
   • Hash jadual untuk carian pantas
   • Pokok binari untuk mengekalkan data yang diisih

3. Pertukaran Angkasa vs Masa

   • Kadangkala menggunakan lebih banyak memori boleh meningkatkan kerumitan masa secara mendadak
   • Cache nilai yang kerap diakses

Perangkap Biasa

1. Gelung Tersembunyi

// Looks like O(n), actually O(n²)
array.forEach(item => {
    const index = anotherArray.indexOf(item);  // indexOf is O(n)
});

1. Penggabungan Rentetan dalam Gelung

// Poor performance
let result = '';
for (let i = 0; i < n; i++) {
    result += someString;  // Creates new string each time
}

// Better approach
const parts = [];
for (let i = 0; i < n; i++) {
    parts.push(someString);
}
const result = parts.join('');

Aplikasi Dunia Sebenar

Memahami Big O membantu anda:

• Pilih algoritma dan struktur data yang betul
• Optimumkan kesesakan prestasi
• Buat keputusan seni bina yang lebih baik
• Lulus temu duga teknikal

Sumber Tambahan

• Pengenalan kepada Algoritma - Sumber akademik yang komprehensif
• Big O Cheat Sheet - Rujukan pantas untuk operasi biasa
• Visualgo - Visualisasikan algoritma dan struktur data

Kesimpulan

Big O Notation mungkin kelihatan akademik, tetapi ia adalah alat praktikal untuk menulis kod yang lebih baik. Mulakan dengan asas ini dan anda akan terus menulis algoritma yang lebih cekap.

---

Apakah pengalaman anda dengan pengoptimuman algoritma? Kongsi pendapat dan soalan anda dalam ulasan di bawah!

Atas ialah kandungan terperinci Notasi Big O untuk Pemula: Panduan Praktikal. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!