Notasi Big O: Panduan Mudah

Big O Notation ialah konsep matematik yang digunakan untuk menerangkan prestasi atau kerumitan algoritma dari segi masa dan ruang apabila saiz input bertambah. Ia membantu kami memahami cara masa jalan algoritma meningkat dengan input yang lebih besar, membolehkan perbandingan yang lebih piawai bagi algoritma berbeza.

Mengapa Menggunakan Notasi O Besar?

Apabila membandingkan algoritma, bergantung semata-mata pada masa pelaksanaan boleh mengelirukan. Sebagai contoh, satu algoritma mungkin memproses set data besar-besaran dalam satu jam, manakala satu lagi mengambil masa empat jam. Walau bagaimanapun, masa pelaksanaan boleh berbeza-beza berdasarkan mesin dan proses berjalan lain. Sebaliknya, kami menggunakan Notasi Big O untuk memfokus pada bilangan operasi yang dilakukan, yang memberikan ukuran kecekapan yang lebih konsisten.

Contoh: Menjumlahkan Nombor

Mari kita terokai dua cara untuk mengira jumlah semua nombor dari 1 hingga n:

Pilihan 1: Menggunakan Gelung

function addUpTo(n) {
    let total = 0;
    for (let i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

Pilihan 2: Menggunakan Formula

function addUpTo(n) {
    return n * (n + 1) / 2;
}

Menganalisis Kerumitan

Dalam Pilihan 1, jika n ialah 100, gelung berjalan 100 kali. Sebaliknya, Pilihan 2 sentiasa melaksanakan bilangan operasi tetap (pendaraban, penambahan dan pembahagian). Oleh itu:

• Pilihan 1 ialah O(n): Kerumitan masa berkembang secara linear dengan n.
• Pilihan 2 ialah O(1): Kerumitan masa kekal malar, tanpa mengira saiz input.

Penafian

Walaupun Pilihan 2 melibatkan tiga operasi (pendaraban, penambahan, pembahagian), kami menumpukan pada aliran umum dalam analisis Big O. Oleh itu, daripada menyatakannya sebagai O(3n), kami memudahkannya menjadi O(n). Begitu juga, O(n 10) memudahkan kepada O(n), dan O(n^2 5n 8) memudahkan kepada O(n^2). Dalam Big O Notation, kami menganggap senario terburuk, di mana istilah tertib tertinggi mempunyai kesan yang paling besar pada prestasi.

Terdapat bentuk tatatanda lain di luar kerumitan lazim yang disenaraikan di atas, seperti kerumitan masa logaritma yang dinyatakan sebagai O(log n).

Apakah Notasi Big O?

Notasi O Besar membolehkan kami memformalkan pertumbuhan masa jalan algoritma berdasarkan saiz input. Daripada memfokuskan pada kiraan operasi tertentu, kami mengkategorikan algoritma ke dalam kelas yang lebih luas termasuk:

• Masa Malar: O(1) - Prestasi algoritma tidak berubah dengan saiz input.
• Masa Linear: O(n) - Prestasi berkembang secara linear dengan saiz input.
• Masa Kuadratik: O(n^2) - Prestasi meningkat secara kuadratik apabila saiz input bertambah.

Contoh O(n^2)

Pertimbangkan fungsi berikut, yang mencetak semua pasangan nombor dari 0 hingga n:

function addUpTo(n) {
    let total = 0;
    for (let i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

Dalam kes ini, fungsi mempunyai dua gelung bersarang, jadi apabila nnn meningkat, bilangan operasi meningkat secara kuadratik. Untuk n= 2, terdapat 4 operasi, dan untuk n=3, terdapat 9 operasi, membawa kepada O(n^2).

Contoh lain: Kira Naik dan Turun

function addUpTo(n) {
    return n * (n + 1) / 2;
}

Pada pandangan pertama, seseorang mungkin menganggap ini O(n^2) kerana ia mengandungi dua gelung. Walau bagaimanapun, kedua-dua gelung berjalan secara bebas dan skala secara linear dengan n. Oleh itu, kerumitan masa keseluruhan ialah O(n).

Memudahkan Analisis

Menganalisis setiap aspek kerumitan kod boleh menjadi rumit, tetapi beberapa peraturan am boleh memudahkan perkara:

• Operasi aritmetik dianggap masa tetap.
• Tugasan boleh ubah ialah masa yang tetap.
• Mengakses elemen dalam tatasusunan (mengikut indeks) atau objek (mengikut kunci) ialah masa tetap.
• Untuk gelung, kerumitan ialah panjang gelung didarab dengan kerumitan apa yang berlaku di dalam gelung.

Kerumitan Ruang

Walaupun kami telah memfokuskan pada kerumitan masa, anda juga boleh mengira kerumitan ruang (memori) menggunakan Big O. Sesetengah orang memasukkan saiz input dalam pengiraan mereka, tetapi selalunya lebih berguna untuk memfokuskan pada ruang yang diperlukan oleh algoritma sahaja sendiri.

Peraturan untuk Kerumitan Ruang (berdasarkan JavaScript):

• Kebanyakan nilai primitif (boolean, nombor, dll.) ialah ruang malar.
• Rentetan memerlukan ruang O(n) (di mana n ialah panjang rentetan).
• Jenis rujukan (susunan, objek) biasanya O(n), dengan n ialah panjang tatasusunan atau bilangan kekunci dalam objek.

Contoh

function printAllPairs(n) {
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
            console.log(i, j);
        }
    }
}

Dalam fungsi ini, kerumitan ruang ialah O(1) kerana kami menggunakan jumlah ruang yang tetap (dua pembolehubah) tanpa mengira saiz input.

Untuk fungsi yang mencipta tatasusunan baharu:

function countUpAndDown(n) {
    console.log("Going up!");
    for (var i = 0; i < n; i++) {
        console.log(i);
    }
    console.log("At the top!\nGoing down...");
    for (var j = n - 1; j >= 0; j--) {
        console.log(j);
    }
    console.log("Back down. Bye!");
}

Di sini, kerumitan ruang ialah O(n) kerana kami memperuntukkan ruang untuk tatasusunan baharu yang berkembang dengan saiz tatasusunan input.

Kesimpulan

Big O Notation menyediakan rangka kerja untuk menganalisis kecekapan algoritma dengan cara yang bebas daripada perkakasan dan butiran pelaksanaan khusus. Memahami konsep ini adalah penting untuk membangunkan kod yang cekap, terutamanya apabila saiz data berkembang. Dengan memfokuskan pada cara skala prestasi, pembangun boleh membuat pilihan termaklum tentang algoritma yang hendak digunakan dalam aplikasi mereka.

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