Skip to content

Latest commit

 

History

History
132 lines (76 loc) · 7.54 KB

README.md

File metadata and controls

132 lines (76 loc) · 7.54 KB

BigOCheatSheet

Pengenalan

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.

ilustrasi_big_notation

🔝 kembali ke atas

Kompleksitas Komputasi Asimtotik

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.

🔝 kembali ke atas

Asimtot

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

function of 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.

🔝 kembali ke atas

Analisis Asimtot

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.

🔝 kembali ke atas

Big O

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

bigO_gfg

🔝 kembali ke atas

Big Ω

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

bigomega_gfg

🔝 kembali ke atas

Big θ

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

bigtheta_gfg

🔝 kembali ke atas

Perbedaan Ketiganya

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)

🔝 kembali ke atas

Konteks Kasus Terburuk, Terbaik, Rata-rata

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)

🔝 kembali ke atas

Referensi

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

🔝 kembali ke atas