Mengapa Big O diajar bukannya Big Theta?

21

Notasi O besar memberikan batas atas untuk suatu fungsi sedangkan Big Theta memberikan batasan yang ketat. Namun saya menemukan bahwa notasi Big O biasanya (dan informal) diajarkan dan digunakan ketika mereka benar-benar berarti Big Theta.

mis. "Quicksort adalah O (N ^ 2)" dapat berubah menjadi pernyataan yang jauh lebih kuat "Quicksort adalah Θ (N ^ 2)"

Meskipun penggunaan Big O secara teknis benar, bukankah penggunaan Big Theta yang lebih umum akan lebih ekspresif dan menyebabkan lebih sedikit kebingungan? Adakah alasan historis mengapa Big O ini lebih umum digunakan?

Catatan Wikipedia :

Secara informal, terutama dalam ilmu komputer, notasi Big O sering diizinkan untuk agak disalahgunakan untuk menggambarkan ikatan ketat asimptotik di mana menggunakan notasi Big Th Th mungkin lebih sesuai secara faktual dalam konteks tertentu.

notation big-o big-theta tskuzzy
sumber
3
Saya tahu ini tidak benar-benar berkaitan dengan pertanyaan, tetapi quicksort bukan theta (N ^ 2). Ini O (N ^ 2).
jsternberg
Big O adalah apa yang perlu diketahui oleh pemula / non-CS. Big Theta adalah apa yang tercakup dalam pengantar algoritma, yang tidak akan diambil oleh setiap jurusan. Mereka yang memiliki kelas algoritma dapat membaca notasi Big O lebih dalam jika mereka mau. Saya tidak yakin apa yang dimaksud kutipan Wikipedia. Dengan publikasi akademis Anda akan mendapatkan celah tenggorokan Anda di sebuah konferensi jika Anda membingungkan Big O dan Theta besar. Beberapa orang menghabiskan seluruh hidup mereka mengejar Theta dan itu adalah masalah SULIT KERAS.
Ayub
@ jsternberg Secara teknis Anda benar. Ini juga benar, tetapi tidak berarti: "Quicksort dalam hal apa pun (terburuk, terbaik, ...) adalah O (n ^ 100). Tapi saya setuju dengan OP itu harus lebih akurat: QuickSort terburuk adalah Theta (N ^ 2), kasus terbaik QuickSort adalah Theta (NlogN) .Karena dalam setiap kasus kita akan mendapatkan fungsi yang berbeda
Eldar

Jawaban:

26

Karena Anda biasanya hanya tertarik pada kasus terburuk ketika menganalisis kinerja. Dengan demikian, mengetahui batas atas sudah cukup.

Ketika berjalan lebih cepat dari yang diharapkan untuk input yang diberikan - itu ok, itu bukan titik kritis. Sebagian besar informasi dapat diabaikan.

Beberapa algoritma, seperti dicatat oleh @Peter Taylor, tidak memiliki ikatan yang kuat sama sekali. Lihat quicksort misalnya O (n ^ 2) dan Omega (n).

Selain itu, batas yang ketat seringkali lebih sulit untuk dihitung.

Lihat juga:

Elang
sumber
6
Tetapi Big O tidak selalu sesuai dengan kinerja kasus terburuk. Saya bisa mengatakan quicksort berjalan di O (2 ^ n) dan 100% benar. Akan jauh lebih bermakna jika saya katakan algoritma X berjalan di Theta (N ^ 2) daripada O (N ^ 2).
tskuzzy
Juga, batas ketat hampir selalu dihitung ketika menganalisis algoritma, bukan hanya batas atas. Saya bertanya mengapa orang tidak hanya menggunakan notasi theta yang jauh lebih ekspresif ketika mereka bisa.
tskuzzy
9
Saya katakan mengapa sebagian besar programmer tidak menggunakannya. Kami malas dan tidak membutuhkan ketelitian. Tidak ada yang menghentikan Anda dari menggunakan theta besar jika Anda mau. Silakan, lakukan itu. Pilihan algoritme Anda kemungkinan besar tidak akan mendapat manfaat sebanyak itu. Saya belum pernah mendengar seorang programmer bingung dengan notasi O besar. Saya juga tidak menganggapnya membingungkan sama sekali.
Falcon
9

Salah satu alasannya adalah bahwa ada banyak kasus di mana Θ tidak diketahui. Sebagai contoh, perkalian Matriks adalah O (n ^ 2.376) tetapi tidak ada batasan yang diketahui. Tentu, sejauh yang saya tahu, ada adalah ketat menuju Matrix perkalian, tapi kita tidak tahu nilainya.

MSalters
sumber
Tapi itu akan menjadi batasan untuk waktu berjalan masalah, bukan algoritma tertentu. Sementara perkalian matriks secara umum dapat diselesaikan lebih cepat dari waktu kubik, algoritma naifnya adalah Θ (n ^ 3) tidak peduli apa.
tskuzzy
5
@tskuzzy, ambil quicksort. Itu tidak memiliki ikatan Theta, karena itu O (n ^ 2) dan Omega (n).
Peter Taylor