- Pengenalan
- Kompleksitas Komputasi Asimtotik
- Asimtot
- Analisis Asimtot
- Big O
- Big Omega
- Big Theta
- Perbedaan Ketiganya
- Konteks Kasus Terburuk, Terbaik, Rata-rata
- Referensi
Sebelum kita menuju ke situs, kita perlu tahu dahulu apa itu Kompleksitas Komputasi Asimtotik. Jika dirimu sudah familiar dengan istilah ini, lewati dan langsung menuju ke Big-O Cheat Sheet Website.
Dalam teori kompleksitas komputasi, kompleksitas komputasi asimtotik merupakan penggunaan analisis asimtotik untuk estimasi kompleksitas komputasi algoritme dan masalah komputasi, yang umumnya dikaitkan dengan penggunaan notasi big O. - Wikipedia
Untuk memahami istilah-istilah tersebut, kita perlu tahu dahulu apa itu Asimtot sebelum kita menyelam dalam Analisis Asimtotik.
Dalam geometri analitis, asimtot dari sebuah kurva adalah sebuah garis yang sedemikian rupa sehingga jarak antara kurva dan garis tersebut mendekati nol seiring x atau y (salah satu atau keduanya) mendekati takhingga. - Wikipedia
Berikut contoh visual dari jarednielsen
y = 1/x
Tak peduli seberapa besar atau kecil nilai x, kurva tidak akan pernah menyentuh sumbu x atau y. Bahkan jika nilainya takhingga. 🐢🏃♀️.Terutama jika nilainya nol. Mengapa? Secara matematis tidak mungkin untuk membagi dengan nol. Pada grafik diatas, sumbu x dan y merupakan asimtot dari persamaan
y = 1 / x. Namun garis apapun bisa menjadi asimtot. Tidak terbatas pada garis horizontal dan vertikal. - jarednielsen
Sekarang kita dapat ide tentang asimtot, ayo lanjut mempelajari mengenai Analisis Asimtotik.
Dalam analisis matematis, analisis asimtotik, juga disebut sebagai _asimtotik merupakan metode untuk menggambarkan perilaku limit. - Wikipedia
Sebagai contoh kita dapat dari jarednielsen. Diberikan fungsi f(x) = x^2 + 2x, dimana x nilainya meningkat (mendekati takhingga) dan 2x menjadi tak signifikan dibandingkan dengan x^2. Sederhananya, kita dapat katakan f(x) ekuivalen secara asimtotik dengan x^2.
Mengapa kita perlu analisis asimtotik ini dirimu mungkin bertanya?
Karena kita perlu mengestimasi kompleksitas komputasional dari algoritme dan masalah komputasional. Agar semua orang sepakat pada hal yang sama, kita menggunakan notasi-notasi ini: big O, big Ω and big θ untuk menggambarkan tipe estimasi yang berbeda.
Big O menggambarkan batas atas suatu algoritme. Inilah mengapa, kita sebagai pengembang dan praktisi terutama peduli dengan Big O. Kita ingin tahu seberapa buruk kinerja suatu algoritme. - jarednielsen
Ini didefinisikan sebagai batas atas dan batas atas pada suatu algoritme merupakan jumlah waktu paling banyak yang dibutuhkan (kinerja kasus terburuk). Notasi Big O digunakan untuk menggambarkan batas atas asimtotik. - GeeksForGeeks
Big Omega menggambarkan batas bawah suatu algoritme. Kalo saja hidup selalu memberi kita array yang diurutkan. 🌼. Kita juga dapat menganggap ini sebagai skenario kasus terbaik kita. - jarednielsen
Ini didefinisikan sebagai batas bawah dan batas bawah pada suatu algoritme merupakan jumlah paling sedikit yang dibutuhkan (cara yang paling efisien, dengan kata lain kasus terbaik). Seperti notasi O menyediakan batas atas asimtotik, notasi Ω menyediakan batas bawah asimtotik. - GeeksForGeeks
Big Theta menggambarkan batasan ketat suatu algoritme, batasannya dari atas dan bawah. Big Theta sering digunakan untuk menggambarkan kasus rata-rata atau yang diharapkan untuk suatu algoritme. Ini tidak sepenuhnya benar, tetapi ini adalah singkatan yang berguna. - jarednielsen
Ini didefinisikan sebagai batas terketat dan batas terketat merupakan yang terbaik dari semua waktu kasus terburuk yang dapat diambil oleh algoritme. - GeeksForGeeks
| Big O | Big Ω / Omega | Big θ / Theta | |
|---|---|---|---|
| Operator bersyarat | <= |
>= |
== |
| Tingkat pertumbuhan suatu algoritme / struktur data | kurang dari | lebih dari | sama dengan |
| Batas | atas | bawah | atas dan bawah |
| Notasi | O(n) |
Ω(n) |
θ(n) |
Apa hubungan antara
kasus terbaik / kasus terburuk / kasus diharapkan
dengan
Big O / Big Omega (Ω) / Big Theta (θ)?
Tidak ada.
Ekuivalensi sering dibuat antara Big O dan kasus terburuk, Big Omega dan kasus terbaik, dan Big Theta dan kasus rata-rata untuk setiap notasi. - jarednielsen
Misalnya, setiap pernyataan mengenai kasus terburuk berikut ini semuanya benar:
Tingkat pertumbuhan kasus terburuk Insertion Sort paling tinggi
O(n^2)
Tingkat pertumbuhan kasus terburuk Insertion Sort paling rendahΩ(n)
Tingkat pertumbuhan kasus terburuk Insertion Sort tepatΘ(n^2)
Big-O Cheat Sheet Website ◽ diakses terakhir 17 September 2022
Asymptotic computational complexity ◽ diakses terakhir 17 September 2022
Asimtot ◽ diakses terakhir 17 September 2022
Asymptotic analysis ◽ diakses terakhir 17 September 2022
What’s the Difference Between Big O, Big Omega, and Big Theta? ◽ diakses terakhir 17 September 2022
Difference between Big Oh, Big Omega and Big Theta ◽ diakses terakhir 17 September 2022