Saya seorang programmer dan baru saja mulai membaca Algoritma. Saya tidak sepenuhnya yakin dengan notasi yaitu Bog Oh, Big Omega dan Big Theta. Alasannya adalah dengan definisi Big Oh, ia menyatakan bahwa harus ada fungsi g (x) sehingga selalu lebih besar atau sama dengan f (x). Atau f (x) <= cn untuk semua nilai n> n0.
Mengapa kita tidak menyebutkan nilai konstan dalam definisi? Misalnya, katakanlah fungsi 6n + 4, kami menyatakannya sebagai O (n). Tapi itu tidak benar bahwa definisi itu berlaku untuk semua nilai konstan. Ini berlaku hanya ketika c> = 10 dan n> = 1. Untuk nilai yang lebih rendah dari c dari 6, nilai n0 meningkat. Jadi mengapa kita tidak menyebutkan nilai konstan sebagai bagian dari definisi?
big-o
algorithm-analysis
Pradeep
sumber
sumber
Jawaban:
Ada beberapa alasan, tetapi mungkin yang paling penting adalah bahwa konstanta adalah fungsi dari implementasi algoritma, bukan algoritma itu sendiri. Urutan suatu algoritma berguna untuk membandingkan algoritme terlepas dari implementasinya.
Runtime aktual quicksort biasanya akan berubah jika diterapkan dalam C atau Python atau Scala atau Postscript. Hal yang sama berlaku untuk bubble sort - runtime akan sangat bervariasi berdasarkan implementasi.
Namun, apa yang tidak akan berubah adalah kenyataan bahwa, semua yang lain sama, karena set data semakin besar waktu yang diperlukan untuk menjalankan semacam gelembung akan meningkat lebih cepat daripada waktu yang diperlukan untuk menjalankan quicksort dalam kasus umum, tidak peduli apa bahasa atau mesin mereka diimplementasikan dengan, dengan asumsi implementasi yang cukup benar. Fakta sederhana ini memungkinkan Anda membuat kesimpulan cerdas tentang algoritme itu sendiri ketika detail konkret tidak tersedia.
The agar suatu algoritma filter keluar faktor yang, sementara penting dalam pengukuran dunia nyata yang sebenarnya, cenderung hanya menjadi kebisingan ketika membandingkan algoritma secara abstrak.
sumber
O (n) dan notasi urutan lainnya (biasanya) tidak berkaitan dengan perilaku fungsi untuk nilai-nilai kecil. Ini berkaitan dengan perilaku fungsi untuk nilai-nilai yang sangat besar, yaitu batas ketika n bergerak menuju tak terhingga.
Konstanta secara teknis penting tetapi mereka biasanya diabstraksi ketika n menjadi cukup besar, nilai c sama sekali tidak relevan. Jika nilai c adalah penting, kita dapat memasukkannya dalam analisis tetapi kecuali jika fungsi yang dibandingkan memiliki faktor konstan yang sangat besar atau jika efisiensi merupakan masalah yang sangat penting, mereka biasanya tidak.
sumber
Notasi O Besar sesuai definisi menyatakan bahwa: Notasi O besar dibangun di atas intuisi bahwa untuk semua nilai n pada dan di sebelah kanan n ', nilai f (n) berada pada atau di bawah cg (n). Konstanta juga tidak masalah ketika Anda pergi ke faktor (variabel) bernilai tinggi (seperti n-square atau n-cube) karena mereka hanya konstanta dan bukan jumlah yang bervariasi yang dapat menjadi sebesar faktor-faktor tersebut. Diberikan di bawah ini adalah grafik notasi Big-O.
For a given function g(n), we denote by O(g(n)) the set of functions:
O(g(n)) = {f(n): there exist positive constants c and n' such that 0<=f(n)<=c.g(n) for all n > n'}
Inti dari notasi ini adalah pada kenyataan "
how lower is f(n) from c.g(n) and not when it starts becoming lower
".sumber
Dalam analisis algoritma, Urutan Pertumbuhan adalah abstraksi kunci dan memberikan tingkat perubahan waktu berjalan seiring perubahan ukuran input. Katakanlah suatu algoritma memiliki waktu berjalan
f(n) = 2n + 3
. Sekarang kita pasang beberapa ukuran input,Seperti dapat dilihat, urutan pertumbuhan terutama ditentukan oleh variabel
n
; konstanta 2 dan 3 kurang signifikan dan ketika ukuran input bertambah, mereka menjadi semakin tidak signifikan dalam menentukannya. Inilah sebabnya mengapa dalam analisis algoritma, konstanta mereda mendukung variabel menentukan urutan pertumbuhan suatu fungsi.sumber
Seluruh gagasan notasi Big-Oh adalah khusus untuk mengabaikan konstanta dan menyajikan bagian terpenting dari fungsi yang menggambarkan run-time dari suatu algoritma.
Lupakan definisi formal sejenak. Fungsi manakah yang lebih buruk (lebih cepat tumbuh),
n^2 - 5000
atau5000 n + 60000
? Untukn
kurang dari sekitar 5000, fungsi linear lebih besar (dan dengan demikian lebih buruk). Di luar itu (nilai tepat 5013?), Persamaan kuadrat lebih besar.Karena ada lebih banyak (lebih sedikit) angka positif lebih besar dari 5000 daripada kurang, kita menganggap kuadrat menjadi fungsi 'lebih besar' (lebih buruk) secara umum. Notasi pesanan (Big-Oh, dll) memberlakukan itu (Anda selalu dapat menghilangkan konstanta tambahan dan multiplikatif menggunakan definisi tersebut).
Tentu saja, semuanya tidak selalu sederhana. Kadang-kadang Anda tidak ingin tahu konstanta tersebut. Manakah yang lebih baik jenis Penyisipan atau semacam Bubble? Keduanya
O(n^2)
. Tapi yang satu benar-benar lebih baik dari yang lain. Dengan analisis yang lebih rumit, Anda bisa mendapatkan konstanta seperti yang Anda tanyakan. Biasanya lebih mudah untuk menghitung fungsi Big-Oh daripada fungsi yang lebih tepat.Big-Oh mengabaikan konstanta ini untuk menyederhanakan dan membuat perbandingan yang paling penting menjadi lebih mudah. Kami menyukai notasi karena biasanya kami tidak ingin tahu tentang konstanta (kebanyakan tidak relevan).
sumber
(karena ini adalah jawaban yang lebih panjang, bacalah tebal untuk ringkasan )
Mari kita ambil contoh Anda dan berjalan melalui langkah demi langkah, memahami tujuan di balik apa yang kami lakukan. Kami mulai dengan fungsi Anda dan tujuan menemukan notasi Oh Besarnya:
Pertama, biarkan
O(g(n))
notasi Big Oh yang kita carif(n)
. Dari definisi Big Oh, kita perlu menemukan yang disederhanakan dig(n)
mana ada beberapa konstantac
dan din0
manac*g(n) >= f(n)
berlaku untuk semuan
lebih besar darin0
.Pertama, mari kita pilih
g(n) = 6n + 4
(yang akan menghasilkanO(6n+4)
Big Oh). Dalam hal ini kita melihat bahwac = 1
dan nilai apa punn0
akan memenuhi persyaratan matematika dari definisi Big Oh, karenag(n)
selalu sama denganf(n)
:Pada titik ini kami telah memenuhi persyaratan matematika. Jika kita berhenti di
O(6n+4)
, jelas bahwa ini tidak lebih membantu daripada menulisf(n)
, sehingga akan kehilangan tujuan sebenarnya dari notasi Oh Besar: untuk memahami kompleksitas waktu umum dari suatu algoritma! Jadi, mari kita beralih ke langkah selanjutnya: penyederhanaan.Pertama, bisakah kita menyederhanakan dari
6n
Big OhO(4)
? Tidak! (Latihan untuk pembaca jika mereka tidak mengerti mengapa)Kedua, dapatkah kita menyederhanakan
4
the Big OhO(6n)
? Iya! Dalam hal itug(n) = 6n
,, jadi:Pada titik ini, mari kita pilih
c = 2
sejak saat itu sisi kiri akan meningkat lebih cepat (sebesar 12) daripada sisi kanan (sebesar 6) untuk setiap kenaikann
.Sekarang kita perlu menemukan yang positif di
n0
mana persamaan di atas benar untuk semuan
lebih besar dari nilai itu. Karena kita sudah tahu bahwa sisi kiri meningkat lebih cepat daripada yang kanan, yang harus kita lakukan adalah menemukan satu solusi positif. Dengan demikian, karenan0 = 2
membuat hal di atas benar, kita tahu itug(n)=6n
, atauO(6n)
berpotensi notasi Oh Besarf(n)
.Sekarang, bisakah kita menyederhanakan
6
the Big OhO(n)
? Iya! Dalam hal itug(n) = n
,, jadi:Mari kita pilih
c = 7
karena yang kiri akan meningkat lebih cepat daripada yang kanan.Kami melihat bahwa di atas akan berlaku untuk semua yang
n
lebih besar atau sama dengann0 = 4
. Dengan demikian,O(n)
notasi Big Oh potensial untukf(n)
. Bisakah kita menyederhanakang(n)
lagi? Nggak!Akhirnya, kami menemukan bahwa notasi Big Oh yang paling sederhana
f(n)
adalahO(n)
. Kenapa kita harus melalui semua ini? Karena sekarang kita tahu bahwaf(n)
itu linier , karena notasi Big Oh adalah kompleksitas linierO(n)
. Yang menyenangkan adalah bahwa sekarang kita dapat membandingkan kompleksitas waktuf(n)
dengan algoritma lainnya! Sebagai contoh, kita sekarang tahu bahwaf(n)
adalah sebanding waktu-kompleksitas fungsih(n) = 123n + 72
,i(n) = n
,j(n) = .0002n + 1234
, dll; karena menggunakan proses penyederhanaan yang sama yang diuraikan di atas mereka semua memiliki kompleksitas waktu linearO(n)
.Manis!!!
sumber
O(4)
, itu akan membuat persamaan ketimpangan kitac*4 >= 6n+4
, dan untuk apa pun yangc
kita pilih, kita selalu bisa menemukan nilai di mana semua nilai din
atas yang akan membuat ketidaksetaraan salah.c
dann0
tidak penting. Yang penting adalah yangn0
ada untukc
kita pilih. Agar hal ini benar, sisi kiri ketidaksetaraan harus meningkat lebih cepat daripada sisi kanan untuk nilai besarn
.c=6
tidak baik untuk ini (6n >= 6n+4
tidak pernah benar), jadi saya memilihc=7
. Saya bisa saja dengan mudah memilihc=10
,,c=734
atauc=6.0000001
dan masih akan dapat melihat bahwa ada beberapan0
yang ada untuk membuat ketidaksetaraan menjadi benarn >= n0
, yang berarti Oh Besar yang kami uji valid.Jika Anda memiliki fungsi kinerja
6n + 4
, pertanyaan yang relevan adalah, "6 apa?". Sebagai satu komentar bertanya: apa yang diwakili konstanta Anda? Dalam istilah fisika, apa unit faktor konstan Anda?Alasan mengapa notasi O () begitu banyak digunakan untuk menggambarkan kinerja algoritma adalah bahwa tidak ada cara portabel untuk menjawab pertanyaan itu. Prosesor yang berbeda akan mengambil jumlah siklus clock yang berbeda dan jumlah waktu yang berbeda untuk melakukan perhitungan elementer yang sama, atau mereka mungkin menyamakan perhitungan elementer yang relevan secara berbeda. Bahasa komputer yang berbeda, atau deskripsi formal dan informal yang berbeda seperti kodesemu, akan mewakili algoritma dengan cara yang sulit untuk dibandingkan secara langsung. Bahkan implementasi dalam bahasa yang sama dapat mewakili algoritma yang sama dengan cara yang berbeda - detail format sepele seperti jumlah baris di samping, Anda umumnya akan memiliki berbagai pilihan struktural yang sewenang-wenang untuk mengimplementasikan algoritma yang diberikan.
Lihatlah dengan cara lain: kami menggunakan "algoritma" tidak untuk menggambarkan implementasi tertentu, tetapi untuk menggambarkan seluruh kelas dari implementasi potensial dari prosedur umum yang sama. Abstraksi ini mengabaikan detail implementasi demi mendokumentasikan sesuatu yang bernilai umum, dan faktor kinerja konstan adalah salah satu dari detail ini.
Yang mengatakan, deskripsi algoritma sering disertai dengan cerita rakyat, catatan, atau bahkan tolok ukur aktual yang menggambarkan kinerja implementasi aktual pada perangkat keras yang sebenarnya. Ini memberi Anda gambaran kasar faktor konstan apa yang diharapkan, tetapi juga harus diambil dengan sebutir garam karena kinerja aktual tergantung pada hal-hal seperti berapa banyak pekerjaan yang dilakukan untuk mengoptimalkan implementasi yang diberikan. Juga, dalam jangka panjang, kinerja relatif dari algoritma yang sebanding cenderung melayang ketika arsitektur prosesor terbaru dan terhebat berubah ...
sumber