Dalam tutorial ini, anda akan mengetahui apa itu notasi asimtotik. Anda juga akan belajar mengenai notasi Big-O, notasi Theta dan notasi Omega.
Kecekapan algoritma bergantung pada jumlah masa, penyimpanan dan sumber lain yang diperlukan untuk melaksanakan algoritma. Kecekapan diukur dengan bantuan notasi asimptotik.
Algoritma mungkin tidak mempunyai prestasi yang sama untuk pelbagai jenis input. Dengan peningkatan saiz input, prestasi akan berubah.
Kajian perubahan prestasi algoritma dengan perubahan urutan ukuran input ditakrifkan sebagai analisis asimptotik.
Notasi Asimptotik
Notasi asimptotik adalah notasi matematik yang digunakan untuk menggambarkan masa berjalan algoritma apabila input cenderung ke arah nilai tertentu atau nilai yang membatasi.
Contohnya: Dalam urutan gelembung, apabila susunan input sudah disusun, masa yang diambil oleh algoritma adalah linear iaitu kes terbaik.
Tetapi, apabila tatasusunan input berada dalam keadaan terbalik, algoritma memerlukan masa maksimum (kuadratik) untuk menyusun elemen iaitu keadaan terburuk.
Apabila susunan input tidak disusun atau dalam urutan terbalik, maka memerlukan waktu rata-rata. Tempoh ini dilambangkan menggunakan notasi asimtotik.
Terdapat tiga notasi asimptotik:
- Notasi Big-O
- Notasi Omega
- Notasi Theta
Notasi Big-O (Notasi O)
Notasi Big-O mewakili batas atas masa berjalan algoritma. Oleh itu, ia memberikan kerumitan algoritma yang paling teruk.
Big-O memberikan bahagian atas fungsi
O (g (n)) = (f (n): terdapat pemalar positif c dan n 0 sehingga 0 ≦ f (n) ≦ cg (n) untuk semua n ≧ n 0 )
Ungkapan di atas dapat digambarkan sebagai fungsi f(n)kepunyaan set O(g(n))jika ada pemalar positif csehingga terletak di antara 0dan cg(n), untuk cukup besar n.
Untuk sebarang nilai n, masa berjalan algoritma tidak melepasi masa yang disediakan oleh O(g(n)).
Oleh kerana ia memberikan masa berjalan terburuk dari algoritma, ia digunakan secara meluas untuk menganalisis algoritma kerana kita selalu tertarik dengan senario terburuk.
Notasi Omega (Ω-notasi)
Notasi omega mewakili batas bawah masa berjalan algoritma. Oleh itu, ia memberikan kerumitan kes terbaik bagi algoritma.
Omega memberikan bahagian bawah fungsi
Ω (g (n)) = (f (n): terdapat pemalar positif c dan n 0 sehingga 0 ≦ cg (n) ≦ f (n) untuk semua n ≧ n 0 )
Ungkapan di atas dapat digambarkan sebagai fungsi f(n)tergolong dalam set Ω(g(n))jika ada pemalar positif csehingga terletak di atas cg(n), untuk cukup besar n.
Untuk sebarang nilai n, masa minimum yang diperlukan oleh algoritma diberikan oleh Omega Ω(g(n)).
Notasi Theta (notasi Θ)
Notasi theta merangkumi fungsi dari atas dan bawah. Oleh kerana ia mewakili batas atas dan bawah masa berjalan algoritma, ia digunakan untuk menganalisis kerumitan kes rata-rata algoritma.
Theta mengikat fungsi dalam faktor pemalar
Untuk fungsi g(n), Θ(g(n))diberikan oleh hubungan:
Θ (g (n)) = (f (n): terdapat pemalar 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 )
Ungkapan di atas dapat digambarkan sebagai fungsi f(n)milik himpunan Θ(g(n))jika ada pemalar positif dan sedemikian rupa sehingga dapat diapit antara dan , untuk n yang cukup besar.c1c2c1g(n)c2g(n)
Sekiranya fungsi f(n)terletak di mana sahaja di antara dan untuk semua , maka dikatakan tidak terikat secara asimtotik.c1g(n)c2g(n)n ≧ n0f(n)
