Dalam tutorial ini, Anda akan mempelajari apa itu notasi asimtotik. Selain itu, Anda akan belajar tentang notasi Big-O, notasi Theta dan notasi Omega.
Efisiensi algoritme bergantung pada jumlah waktu, penyimpanan, dan sumber daya lain yang diperlukan untuk menjalankan algoritme. Efisiensi diukur dengan bantuan notasi asimtotik.
Algoritme mungkin tidak memiliki kinerja yang sama untuk jenis input yang berbeda. Dengan bertambahnya ukuran input, kinerja akan berubah.
Studi tentang perubahan kinerja algoritma dengan perubahan urutan ukuran input didefinisikan sebagai analisis asimtotik.
Notasi Asymptotic
Notasi asimtotik adalah notasi matematika yang digunakan untuk mendeskripsikan waktu berjalan suatu algoritme ketika input cenderung ke nilai tertentu atau nilai pembatas.
Misalnya: Dalam bubble sort, ketika larik masukan sudah diurutkan, waktu yang dibutuhkan oleh algoritme adalah linier, yaitu kasus terbaik.
Namun, ketika larik masukan berada dalam kondisi terbalik, algoritme memerlukan waktu maksimum (kuadrat) untuk mengurutkan elemen yaitu kasus terburuk.
Ketika larik masukan tidak diurutkan atau dalam urutan terbalik, maka dibutuhkan waktu rata-rata. Durasi ini dilambangkan dengan notasi asimtotik.
Terutama ada tiga notasi asimtotik:
- Notasi Big-O
- Notasi omega
- Notasi theta
Notasi Big-O (Notasi-O)
Notasi Big-O mewakili batas atas dari waktu berjalan suatu algoritma. Dengan demikian, ini memberikan kompleksitas kasus terburuk dari suatu algoritma.
Big-O memberikan batas atas suatu fungsi
O (g (n)) = (f (n): terdapat konstanta positif c dan n 0 sehingga 0 ≦ f (n) ≦ cg (n) untuk semua n ≧ n 0 )
Ekspresi di atas dapat dideskripsikan sebagai fungsi yang f(n)termasuk dalam himpunan O(g(n))jika terdapat konstanta positif cyang terletak di antara 0dan cg(n), untuk cukup besar n.
Untuk nilai apa pun n, waktu berjalan suatu algoritme tidak melewati waktu yang disediakan oleh O(g(n)).
Karena memberikan waktu berjalan kasus terburuk dari suatu algoritme, ini banyak digunakan untuk menganalisis algoritme karena kami selalu tertarik pada skenario kasus terburuk.
Notasi Omega (notasi Ω)
Notasi omega mewakili batas bawah dari waktu berjalan suatu algoritma. Dengan demikian, ini memberikan kompleksitas kasus terbaik dari suatu algoritma.
Omega memberikan batas bawah suatu fungsi
Ω (g (n)) = (f (n): terdapat konstanta positif c dan n 0 sehingga 0 ≦ cg (n) ≦ f (n) untuk semua n ≧ n 0 )
Ekspresi di atas dapat dideskripsikan sebagai fungsi yang f(n)termasuk dalam himpunan Ω(g(n))jika terdapat konstanta positif cyang terletak di atas cg(n), untuk cukup besar n.
Untuk nilai berapa pun n, waktu minimum yang dibutuhkan oleh algoritme diberikan oleh Omega Ω(g(n)).
Notasi Theta (notasi Θ)
Notasi teta melingkupi fungsi dari atas dan bawah. Karena mewakili batas atas dan bawah dari waktu berjalan suatu algoritma, ini digunakan untuk menganalisis kompleksitas kasus rata-rata dari suatu algoritma.
Theta membatasi fungsi dalam faktor konstanta
Untuk suatu fungsi g(n), Θ(g(n))diberikan oleh relasi:
Θ (g (n)) = (f (n): ada konstanta positif c 1 , c 2 dan n 0 sehingga 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) untuk semua n ≧ n 0 )
Ekspresi di atas dapat dideskripsikan sebagai fungsi yang f(n)dimiliki oleh himpunan Θ(g(n))jika terdapat konstanta positif dan sedemikian rupa sehingga dapat diapit di antara dan , untuk n yang cukup besar.c1c2c1g(n)c2g(n)
Jika suatu fungsi f(n)terletak di mana saja di antara dan untuk semua , maka dikatakan terikat erat secara asimtotik.c1g(n)c2g(n)n ≧ n0f(n)
