Pembenaran untuk mengabaikan faktor konstan dalam Big O

Seringkali jika kompleksitas memiliki konstanta seperti 3n, kita mengabaikan konstanta ini dan mengatakan O (n) dan bukan O (3n). Saya tidak dapat memahami bagaimana kita bisa mengabaikan perubahan tiga kali lipat seperti itu? Beberapa hal bervariasi 3 kali lebih cepat daripada yang lain! Mengapa kita mengabaikan fakta ini?

Untuk merasionalisasi bagaimana notasi asimptotik mengabaikan faktor konstan, saya biasanya berpikir seperti ini: kompleksitas asimptotik bukan untuk membandingkan kinerja algoritma yang berbeda, itu untuk memahami bagaimana kinerja masing-masing algoritme berskala sehubungan dengan ukuran input.

Misalnya, kita mengatakan bahwa fungsi yang mengambil langkah adalah O ( n ) , karena, secara umum, untuk input yang cukup besar, menggandakan ukuran input tidak akan lebih dari dua kali lipat jumlah langkah yang diambil. Demikian pula, O ( n 2 ) berarti bahwa menggandakan ukuran input paling banyak akan melipatgandakan jumlah langkah, dan O ( log n ) berarti menggandakan ukuran input akan menambah jumlah langkah paling banyak konstanta.$3n$$O(n)$$O(n^2)$$O(\log n)$

Ini alat untuk mengatakan algoritma mana yang lebih baik, bukan yang mana yang lebih cepat.

Pertama, seperti yang sudah dijelaskan oleh jawaban lain, , atau dengan kata lain, fungsi adalah O ( 3 n ) jika dan hanya jika itu adalah O ( n ) . f = O ( 3 n ) berarti ada titik N dan faktor C 3 sehingga untuk semua n ≥ N , f ( n ) ≤ C 3 ⋅ $O(3n) = O(n)$$O(3n)$$O(n)$$f = O(3n)$$N$$C_3$$n \ge N$ . Sekarang pilih C 1 = 3 C 3 : untuk semua n ≥ N , f ( n ) ≤ C 1 ⋅ n , jadi f = O ( n ) . Bukti sebaliknya sama.$f(n) \le C_3 \cdot 3n$$C_1 = 3 C_3$$n \ge N$$f(n) \le C_1 \cdot n$$f = O(n)$

Sekarang dengan alasan mengapa ini adalah alat yang tepat. Perhatikan bahwa ketika kita mengukur kompleksitas suatu algoritma, kita tidak memberikan unit. Kami tidak menghitung detik, atau instruksi mesin: kami menghitung beberapa langkah dasar yang tidak ditentukan yang masing-masing mengambil waktu terbatas. Kami melakukan itu karena mengeksekusi algoritma yang sama pada mesin yang berbeda akan mengubah waktu yang dibutuhkan per instruksi - kalikan frekuensi clock dengan dan waktu eksekusi berubah dari f ( n ) ke f ( n ) /$3$$f(n)$$f(n)/3$. Jika kita menerapkan algoritma yang sama dalam bahasa yang berbeda, atau pada sistem yang berbeda, waktu yang diambil oleh setiap langkah dasar mungkin berbeda, tetapi sekali lagi itu terlalu detail: kita hampir tidak pernah peduli tentang perbedaan seperti itu.

Ketika Anda benar-benar memperhatikan ketepatan waktu, kompleksitas asimptotik tidak relevan: kompleksitas asimptotik memberi tahu Anda apa yang terjadi untuk ukuran input yang sangat besar, yang mungkin atau mungkin bukan ukuran input aktual yang Anda hadapi.

Ingat definisi Big-O:

jika ada c > 0 sehingga f ( n ) ≤ c g ( n ) untuk semua n .$f(n)\in O(g(n))$$c>0$$f(n)\le cg(n)$$n$

Di bawah definisi ini, kita memiliki untuk setiap konstanta d . Tujuan dari notasi O adalah untuk menyederhanakan ekspresi dengan cara ini. Memang, 3 n tumbuh 3 kali lebih cepat dari n , tetapi keduanya linear. Apakah ini dibenarkan atau tidak - itu tergantung pada konteksnya. Tetapi jika Anda setuju untuk menggunakan notasi O , maka menurut definisi ini berlaku.$dn\in O(n)$$d$$O$$3n$$n$$O$

Notasi O besar adalah rata-rata unit bebas untuk mengukur variasi kinerja, sehingga tahan terhadap biaya relatif primitif komputasi.

Singkatnya: Notasi O besar adalah unit bebas, jenis pengukuran relatif (berlawanan dengan pengukuran absolut). Ini hanya dapat mengukur variasi kinerja, bukan kinerja absolut, yang konstanta sangat penting. Keuntungannya adalah ini menjadikannya sebagian besar implementasi independen, dengan memungkinkan analisis lebih sederhana yang dapat mengabaikan biaya relatif dari operasi dasar, selama biaya ini memiliki batas atas dan bawah yang tetap positif. Tetapi konsekuensinya adalah bahwa faktor-faktor konstan tidak ada artinya . Namun, bahkan untuk tujuannya, analisis kompleksitas asimptotik dapat dipertanyakan dengan alasan lain , dan harus dipertimbangkan dengan hati-hati. Misalnya, ukuran input mentah mungkin bukan parameter yang tepat untuk dipertimbangkan.

Komentar pertama adalah bahwa pertanyaan Anda tidak dinyatakan secara akurat. Ketika Anda mengabaikan konstanta in 3 n , memang ada "perubahan tiga kali lipat", tetapi keduanya bervariasi pada tingkat yang sama, dan Anda tidak dapat menyatakan bahwa "[satu] benda bervariasi 3 kali lebih cepat daripada yang lain".$3$$3n$

Alasan yang baik untuk mengabaikan konstanta dalam notasi Landau adalah bahwa kita tidak memiliki unit yang dapat kita andalkan. Ketika seseorang menyatakan bahwa A tinggal dua kali lebih jauh dari Anda daripada B, ini memang memiliki makna terlepas dari unit apa pun. Kita bisa menyetujuinya meskipun Anda mengukur jarak dalam inci sementara saya melakukannya dalam tahun cahaya. Tetapi pengukuran jarak absolut membutuhkan unit yang ditentukan, dan formulasi numeriknya tergantung pada unit yang dipilih.

Waktu aktual yang diambil oleh suatu algoritma tergantung pada waktu pelaksanaan operasi dasar, yang sangat bergantung pada mesin. Anda dapat menghitung jumlah operasi dasar, tetapi tidak ada alasan untuk percaya bahwa mereka semua mengambil waktu yang sama, dan selalu memungkinkan untuk menggabungkan beberapa operasi menjadi satu, atau sebaliknya menguraikan operasi menjadi yang lebih kecil, sehingga jumlahnya operasi tidak benar-benar bermakna, kecuali jika Anda menyetujui mesin virtual referensi. Menjadi referensi independen adalah keuntungan.

Pandangan lain tentang keuntungan dari pendekatan ini adalah bahwa yang Anda pedulikan dalam analisis adalah menghitung jumlah operasi elementer, selama biayanya memiliki batas atas dan batas bawah positif. Anda tidak perlu khawatir tentang biaya individu.

Namun, harga yang harus dibayar untuk keuntungan itu adalah bahwa penilaian biaya perhitungan diberikan dengan unit yang tidak ditentukan, dan waktu perhitungan, misalnya, bisa nanodetik atau milenia - kita bahkan tidak mencoba untuk mengetahuinya. Dengan kata lain faktor konstan tidak ada artinya, karena satuan ganti tidak dapat dipisahkan dari perubahan faktor konstan , dan tidak ada satuan referensi yang digunakan.

Seperti dicatat oleh Patrick87 , ini cukup untuk memahami bagaimana suatu algoritma timbangan sehubungan dengan ukuran input, tetapi itu tidak akan memberikan ukuran kinerja absolut, pendek bergantung pada unit referensi. Melepaskan mesin abstrak referensi umum dapat dilakukan ketika seseorang benar-benar ingin membandingkan kinerja algoritma yang berbeda, tetapi lebih sulit untuk memastikan bahwa perbandingan tidak bias oleh detail realisasi. Dalam kompleksitas asimptotik, risiko ini dihindari karena Anda membandingkan algoritme dengan dirinya sendiri.

$O(n^6)$algoritma yang digunakan untuk ML, yang memiliki kompleksitas kasus terburuk secara eksponensial. Tapi itu sepertinya tidak mengganggu pengguna ML, atau untuk mencegah penulisan program yang sangat besar di ML. Ada lebih dari konstanta yang penting. Sebenarnya, analisis asimptotik menghubungkan ukuran biaya perhitungan dengan ukuran kompleksitas input. Tetapi ukuran mentah mungkin bukan ukuran yang tepat.

Kompleksitas seperti decidability, mungkin secara teori buruk, tetapi itu mungkin tidak relevan untuk sebagian besar ruang data ... kadang-kadang. Analisis kompleksitas asimptotik adalah alat yang baik dan dirancang dengan baik, dengan kelebihan dan keterbatasannya, seperti semua alat. Dengan atau tanpa menjelaskan konstanta, yang mungkin tidak ada artinya, menggunakan penilaian diperlukan.

$O(n)=O(3n)$

$n$$3n$

Ini jauh lebih berguna untuk menebak seberapa cepat suatu algoritma. Kalau tidak, kita harus melihat fungsi sambungan besar-besaran, yang akan sangat sulit untuk dipahami.

Alasan utama lainnya adalah agar pengukuran ini tidak tergantung pada perangkat keras. Kompiler dan arsitektur yang berbeda akan mengubah kode yang sama menjadi set instruksi yang sangat berbeda. Namun, jika kita tahu bahwa jumlah instruksi adalah linier, eksponensial, dll., Maka kita memiliki gagasan tentang kecepatan algoritma yang berlaku, terlepas dari komputer aktual yang kita kompilasi atau jalankan.

$f(n)=O(g(n))$$\limsup\limits_{n\to\infty} \frac{f(n)}{g(n)}<+\infty$

$g(n)=n$$g(n)=3n$

$O(n^2)=O(.00005321n^2+1000000000n+10^{46803})$$f$$=$

Biar saya jelaskan. Mari kita ambil n = 100000. Sekarang, apa itu 3n? Itu 300000 ( Ya, itu adalah 3 lipatan n ) Tapi apa itu n ^ 2 ? 10000000000 . ( ini adalah 1 lakh lipatan n ) .. Bandingkan n ^ 2 dengan n. 3 diabaikan bila kita bandingkan dengan 1 lakh. jadi, kita bisa menghapusnya.

Pikirkan jika n adalah miliaran atau triliunan. Dalam hal ini, sekali lagi kita akan membandingkan 3 dengan miliaran atau triliunan. Sekarang, Anda tahu mengapa kita bisa mengabaikan 3.