Apakah ini "Aturan" yang Tepat untuk Mengidentifikasi Notasi "Big O" dari Algoritma?

Saya telah belajar lebih banyak tentang Notasi O Besar dan bagaimana menghitungnya berdasarkan bagaimana suatu algoritma ditulis. Saya menemukan serangkaian "aturan" yang menarik untuk menghitung algoritma Notasi O Besar dan saya ingin melihat apakah saya berada di jalur yang benar atau jauh.

Notasi O Besar: N

function(n) {
    For(var a = 0; i <= n; i++) { // It's N because it's just a single loop
        // Do stuff
    }
}

Notasi O Besar: N ²

function(n, b) {
    For(var a = 0; a <= n; a++) {
        For(var c = 0; i <= b; c++) { // It's N squared because it's two nested loops
            // Do stuff
        }
    }
}

Notasi O Besar: 2N

function(n, b) {
    For(var a = 0; a <= n; a++) {
        // Do stuff
    }
    For(var c = 0; i <= b; c++) { // It's 2N the loops are outside each other
        // Do stuff
    }
}

Notasi O Besar: NLogN

function(n) {
    n.sort(); // The NLogN comes from the sort?
    For(var a = 0; i <= n; i++) {
        // Do stuff
    }
}

Apakah contoh saya dan notasi selanjutnya benar? Apakah ada notasi tambahan yang harus saya waspadai?

Secara formal, notasi O besar menggambarkan tingkat kerumitan.

Untuk menghitung notasi O besar:

1. mengidentifikasi formula untuk kompleksitas algoritma. Katakanlah, misalnya, dua loop dengan satu lagi bersarang di dalam, kemudian tiga loop tidak bersarang:2N² + 3N
2. hapus semua kecuali istilah tertinggi: 2N²
3. hapus semua konstanta: N²

Dengan kata lain dua loop dengan satu lagi bersarang di dalam, maka tiga loop lainnya tidak bersarang adalah O (N²)

Ini tentu saja mengasumsikan bahwa apa yang Anda miliki di loop adalah instruksi sederhana. Jika Anda memiliki contoh sort()di dalam loop, Anda harus mengalikan kompleksitas loop dengan kompleksitas sort()implementasi yang digunakan bahasa / pustaka dasar Anda.

Jika Anda ingin menganalisis algoritme ini, Anda perlu mendefinisikan // dostuff, karena itu benar-benar dapat mengubah hasilnya. Anggaplah dostuff membutuhkan jumlah operasi O (1) yang konstan.

Berikut adalah beberapa contoh dengan notasi baru ini:

Sebagai contoh pertama Anda, linear traversal: ini benar!

DI):

for (int i = 0; i < myArray.length; i++) {
    myArray[i] += 1;
}

Mengapa itu linear (O (n))? Ketika kita menambahkan elemen tambahan ke input (array), jumlah operasi yang terjadi meningkat sebanding dengan jumlah elemen yang kita tambahkan.

Jadi jika diperlukan satu operasi untuk meningkatkan integer di suatu tempat dalam memori, kita dapat memodelkan pekerjaan yang dilakukan loop dengan f (x) = 5x = 5 operasi tambahan. Untuk 20 elemen tambahan, kami melakukan 20 operasi tambahan. Satu pass array cenderung linier. Begitu juga algoritma seperti bucket sortir, yang dapat mengeksploitasi struktur data untuk melakukan pengurutan dalam satu lintasan tunggal array.

Contoh kedua Anda juga akan benar dan terlihat seperti ini:

O (N ^ 2):

for (int i = 0; i < myArray.length; i++) {
    for (int j = 0; j < myArray.length; j++) {
        myArray[i][j] += 1;
    }
}

Dalam hal ini, untuk setiap elemen tambahan dalam array pertama, i, kita harus memproses SEMUA dari j. Menambahkan 1 ke saya sebenarnya menambahkan (panjang j) ke j. Jadi, Anda benar! Pola ini adalah O (n ^ 2), atau dalam contoh kita sebenarnya O (i * j) (atau n ^ 2 jika i == j, yang sering terjadi dengan operasi matriks atau struktur data persegi.

Contoh ketiga Anda adalah ketika segalanya berubah tergantung pada dostuff; Jika kode seperti yang ditulis dan melakukan hal-hal adalah konstan, itu sebenarnya hanya O (n) karena kita memiliki 2 melewati array ukuran n, dan 2n dikurangi menjadi n. Loop berada di luar satu sama lain bukanlah faktor kunci yang dapat menghasilkan 2 ^ kode; berikut adalah contoh fungsi yang 2 ^ n:

var fibonacci = function (n) {
    if (n == 1 || n == 2) {
        return 1;
    }

    else {
        return (fibonacci(n-2) + fibonacci(n-1));
    }
}

Fungsi ini 2 ^ n, karena setiap panggilan ke fungsi menghasilkan DUA panggilan tambahan ke fungsi (Fibonacci). Setiap kali kita memanggil fungsi, jumlah pekerjaan yang harus kita lakukan berlipat ganda! Ini tumbuh super cepat, seperti memotong kepala hydra dan memiliki dua yang baru tumbuh setiap kali!

Sebagai contoh terakhir Anda, jika Anda menggunakan semacam nlgn seperti merge-sort, Anda benar bahwa kode ini adalah O (nlgn). Namun, Anda dapat mengeksploitasi struktur data untuk mengembangkan jenis yang lebih cepat dalam situasi tertentu (seperti rentang nilai yang diketahui dan terbatas seperti dari 1-100). Namun, Anda benar dalam berpikir, bahwa kode urutan tertinggi mendominasi; jadi jika jenis O (nlgn) berada di sebelah operasi yang membutuhkan waktu kurang dari O (nlgn), kompleksitas waktu totalnya adalah O (nlgn).

Dalam JavaScript (setidaknya di Firefox) jenis default di Array.prototype.sort () memang MergeSort, jadi Anda melihat O (nlgn) untuk skenario terakhir Anda.

Contoh kedua Anda (loop luar dari 0 ke n , loop dalam dari 0 ke b ) adalah O ( nb ), bukan O ( n ² ). Aturannya adalah bahwa Anda menghitung sesuatu n kali, dan untuk masing-masing Anda menghitung sesuatu yang lain b kali, maka pertumbuhan fungsi ini semata-mata tergantung pada pertumbuhan n * b .

Contoh ketiga Anda hanya O ( n ) - Anda dapat menghapus semua konstanta karena mereka tidak tumbuh dengan n dan pertumbuhan adalah tentang notasi Big-O.

Adapun contoh terakhir Anda, ya, notasi Big-O Anda pasti akan datang dari metode sortir yang akan, jika berbasis perbandingan (seperti yang biasanya terjadi), dalam bentuk yang paling efisien, O ( n * logn ) .

Ingatlah bahwa ini adalah perkiraan representasi waktu berjalan. "Aturan praktis" merupakan perkiraan karena tidak tepat tetapi memberikan perkiraan tingkat pertama yang baik untuk tujuan evaluasi.

Run-time yang sebenarnya akan tergantung pada berapa banyak heap-space, seberapa cepat prosesor, set instruksi, penggunaan awalan atau peningkatan operator pasca-perbaikan, dll., Yadda. Analisis run-time yang tepat akan memungkinkan penentuan penerimaan tetapi memiliki dasar-dasar pengetahuan memungkinkan Anda untuk memprogram sejak awal.

Saya setuju Anda berada di jalur yang benar untuk memahami bagaimana Big-O dirasionalisasi dari buku teks ke aplikasi praktis. Itu mungkin rintangan yang sulit untuk diatasi.

Laju pertumbuhan asimptotik menjadi penting pada kumpulan data besar dan program besar, jadi untuk contoh umum Anda menunjukkan tidak penting untuk sintaksis dan logika yang tepat.

Besar oh, menurut definisi berarti: untuk fungsi f (t) terdapat fungsi c * g (t) di mana c adalah konstanta arbitrer sehingga f (t) <= c * g (t) untuk t> n di mana n adalah konstanta arbitrer, maka f (t) ada di O (g (t)) .Ini adalah notasi matematika yang digunakan dalam ilmu komputer untuk menganalisis algoritma. Jika Anda bingung, saya akan merekomendasikan melihat ke dalam hubungan penutupan, dengan cara itu Anda bisa melihat dalam tampilan yang lebih rinci bagaimana algoritma ini mendapatkan nilai-nilai besar-oh ini.

Beberapa konsekuensi dari definisi ini: O (n) sebenarnya sebangun dengan O (2n).

Juga ada banyak jenis algoritma penyortiran. Nilai Big-Oh minimum untuk jenis perbandingan adalah O (nlogn) namun ada banyak jenis dengan big-oh yang lebih buruk. Misalnya sort seleksi memiliki O (n ^ 2). Beberapa jenis non perbandingan mungkin memiliki nilai big-oh yang lebih baik. Semacam ember, misalnya memiliki O (n).