Memahami Notasi Big O dan Kerumitan Masa dalam JavaScript

Apabila bekerja dengan JavaScript, menulis kod berfungsi adalah penting, tetapi memastikan ia berjalan dengan cekap adalah sama penting. Di sinilah Notasi Big O masuk. Ia menyediakan cara untuk menganalisis cara skala prestasi kod anda apabila saiz input meningkat, membantu anda menulis aplikasi yang dioptimumkan dan boleh skala.

Artikel ini akan meneroka asas Notasi Big O dan kerumitan masa biasa dengan contoh mesra pemula dalam JavaScript

Apakah Notasi Big O?

Notasi O Besar ialah perwakilan matematik yang menerangkan kecekapan algoritma. Ia membantu kami memahami:

1. Kerumitan Masa: Bagaimana masa pelaksanaan algoritma berubah mengikut saiz input.
2. Kerumitan Ruang: Cara penggunaan memori algoritma berubah mengikut saiz input.

Matlamatnya adalah untuk menilai prestasi algoritma apabila saiz input berkembang, memfokuskan pada senario terburuk.

---

Mengapa Notasi Big O Penting?

Katakan anda ditugaskan untuk mencari nama dalam buku telefon:

• Satu pendekatan ialah menyelak setiap halaman sehingga anda menemui nama (carian linear).
• Satu lagi ialah bermula di tengah dan secara sistematik menyempitkan (carian binari).

Kedua-dua pendekatan menyelesaikan masalah, tetapi kecekapannya berbeza dengan ketara apabila saiz buku telefon bertambah. Big O membantu kami membandingkan pendekatan ini dan memilih yang terbaik.

---

Notasi O Besar dalam Tindakan

Di bawah ialah kerumitan Big O biasa, dijelaskan dengan contoh praktikal dalam JavaScript.

---

1. O(1) - Masa Malar

Masa jalan kekal sama tanpa mengira saiz input. Operasi ini adalah yang paling cekap.

Contoh: Mengakses elemen dalam tatasusunan mengikut indeks.

const numbers = [10, 20, 30, 40, 50];
console.log(numbers[2]); // Always takes the same time, no matter the array size

---

2. O(log n) - Masa Logaritma

Masa jalan berkembang secara logaritma apabila saiz input bertambah. Ini sering berlaku dalam algoritma bahagi-dan-takluk seperti carian binari.

Contoh: Carian binari pada tatasusunan yang diisih.

function binarySearch(arr, target) {
    let start = 0;
    let end = arr.length - 1;

    while (start <= end) {
        const mid = Math.floor((start + end) / 2);

        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            start = mid + 1; // Search the right half
        } else {
            end = mid - 1; // Search the left half
        }
    }

    return -1; // Target not found
}

const arr = [1, 3, 5, 7, 9];
console.log(binarySearch(arr, 7)); // Output: 3

---

3. O(n) - Masa Linear

Masa jalan berkembang secara berkadar dengan saiz input. Ini berlaku apabila anda perlu memeriksa setiap elemen sekali.

Contoh: Mencari item dalam tatasusunan yang tidak diisih.

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i; // Found
        }
    }
    return -1; // Not found
}

const items = [10, 20, 30, 40, 50];
console.log(linearSearch(items, 30)); // Output: 2

---

4. O(n²) - Masa Kuadratik

Masa jalan berkembang secara kuadratik apabila saiz input meningkat. Ini adalah tipikal dalam algoritma dengan gelung bersarang.

Contoh: Pelaksanaan isihan gelembung asas.

const numbers = [10, 20, 30, 40, 50];
console.log(numbers[2]); // Always takes the same time, no matter the array size

---

5. O(2ⁿ) - Masa Eksponen

Waktu jalan berganda dengan setiap input tambahan. Ini berlaku dalam algoritma yang menyelesaikan masalah secara rekursif, dengan mengambil kira semua penyelesaian yang mungkin.

Contoh: Mengira nombor Fibonacci secara rekursif.

function binarySearch(arr, target) {
    let start = 0;
    let end = arr.length - 1;

    while (start <= end) {
        const mid = Math.floor((start + end) / 2);

        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            start = mid + 1; // Search the right half
        } else {
            end = mid - 1; // Search the left half
        }
    }

    return -1; // Target not found
}

const arr = [1, 3, 5, 7, 9];
console.log(binarySearch(arr, 7)); // Output: 3

---

Menggambarkan Big O

Begini perbandingan kerumitan Big O yang berbeza apabila saiz input meningkat:

Big O	Name	Example Use Case	Growth Rate
O(1)	Constant	Array access	Flat
O(log n)	Logarithmic	Binary search	Slow growth
O(n)	Linear	Looping through an array	Moderate growth
O(n²)	Quadratic	Nested loops	Rapid growth
O(2ⁿ)	Exponential	Recursive brute force	Very fast growth

---

Ilustrasi Kadar Pertumbuhan

Bayangkan anda sedang menyelesaikan masalah, dan saiz input bertambah. Begini cara algoritma dengan skala kerumitan berbeza apabila saiz input meningkat:

Input Size	O(1)	O(log n)	O(n)	O(n²)	O(2ⁿ)
1	1 ms	1 ms	1 ms	1 ms	1 ms
10	1 ms	3 ms	10 ms	100 ms	~1 sec
100	1 ms	7 ms	100 ms	10 sec	~centuries
1000	1 ms	10 ms	1 sec	~17 min	Unrealistic

• O(1) kekal malar tanpa mengira input.
• O(log n) tumbuh dengan perlahan, sesuai untuk input yang besar.
• O(n) berkembang secara berkadar dengan saiz input.
• O(n²) dan lebih tinggi dengan cepat menjadi tidak praktikal untuk input yang besar.

---

Memvisualisasikan Big O dengan Kod

Berikut ialah cara untuk menggambarkan bilangan operasi untuk kerumitan yang berbeza menggunakan pembilang mudah:

const numbers = [10, 20, 30, 40, 50];
console.log(numbers[2]); // Always takes the same time, no matter the array size

---

Salah Faham Biasa Mengenai Big O

1. Big O ≠ Prestasi Sebenar: Big O memberitahu anda cara skala prestasi, bukan masa yang tepat diambil.
   • Sebagai contoh, algoritma O(n) dengan faktor pemalar yang kecil mungkin mengatasi algoritma O(log n) untuk saiz input yang kecil.
2. Kes Terbaik lwn. Kes Terburuk: Big O biasanya menerangkan senario kes terburuk. Contohnya, mencari item yang tiada dalam senarai.
3. Bukan Semua Gelung Bersarang Adalah O(n²): Kerumitan bergantung pada bilangan elemen yang diproses oleh gelung dalam.

---

Petua Praktikal untuk Pemula

1. Fokus pada O(1), O(n) dan O(n²): Ini ialah kerumitan paling biasa yang akan anda hadapi.
2. Ukur Prestasi: Gunakan alatan seperti Chrome DevTools untuk menanda aras kod anda.
3. Refactor for Efficiency: Setelah kod anda berfungsi, kenal pasti bahagian yang mempunyai kerumitan yang lebih tinggi dan optimumkan.
4. Terus Belajar: Platform seperti LeetCode dan HackerRank menyediakan latihan yang hebat untuk memahami Big O.

---

Kesimpulan

Big O Notation ialah alat penting untuk menilai kecekapan algoritma dan memahami cara skala kod anda. Dengan memahami asas dan menganalisis corak biasa, anda akan berjaya menulis aplikasi JavaScript yang berprestasi.

Selamat pengekodan! ?

Atas ialah kandungan terperinci Memahami Notasi Big O dan Kerumitan Masa dalam JavaScript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!