Description

Big-O Notation atau Notasi O Besar adalah salah satu cara untuk mengetahui kecepatan suatu algoritma secara matematis. pada artikel ini kita akan mempelajari tentang Big-O notation dengan menggunakan contoh fungsi faktorial dan faktorisasi dengan bahasa python

Big-O Notation

seperti yang dijelaskan sebelumnya, big-o notation dapat digunakan untuk menganalisis kecepatan dari suatu algoritma dengan tujuan untuk membuat fungsi yang lebih efisien. beberapa contoh dari Big-O notation adalah O(n), O(n), O(log(n)), O(log(n)), O(2n), dan O(n!).

Di atas merupakan contoh grafik berbagai Big-O notation, semakin landai grafik fungsinya maka akan semakin cepat algoritmanya, artinya jika suatu algoritma sebagai fungsi mempunyai Big-O notation sebesar O(n) maka fungsi(5) mempunyai efisiensi sebesar 5, sedangkan jika fungsi tersebut mempunyai Big-O sebesar $O(n^{2})$ maka fungsi(5) mempunyai efisiensi sebesar 25, dan seterusnya untuk notasi big-o lainnya.

Faktorial

Fungsi faktorial adalah fungsi yang menghitung nilai perkalian dari n * n-1 * n-2 * n-3 * …  1. contoh dari perhitungan faktorial adalah 5 * 4 * 3 * 2 * 1 = 120. Jika faktorial ditulis dalam fungsi, maka fungsi factorial(5) = 120, namun fungsi faktorial(5) juga dapat ditulis secara rekursif sebagai factorial(5) = 5 * factorial(4) karena factorial(4) = 4 * 3 * 2 * 1.

Fungsi rekursif merupakan fungsi yang memanggil dirinya sendiri untuk melakukan kalkulasi. Pada contoh diatas fungsi faktorial memanggil dirinya sendiri saat menghitung factorial(5) = 5 * factorial(4). Fungsi rekursif juga memiliki syarat yaitu mempunyai base case agar tidak terpanggil dalam loop, dalam fungsi faktorial base casenya merupakan factorial(0) = 1

berikut ini adalah contoh dari fungsi faktorial dalam bahasa python.

dalam fungsi tersebut, fungsi factorial dipanggil sebanyak n kali, maka dari itu fungsi di atas mempunyai Big-O sebesar O(n).

Menemukan Faktor

Faktor adalah bilangan yang merupakan faktor perkalian dari suatu bilangan. Contohnya proses Faktorisasi dari 100 adalah 1,2,4,5,10,20,25,50,100 karena 1 * 10 = 10, 2 * 5 = 10, 4 * 25 = 100, 5 * 20 = 100, 10 * 10 = 100, 20 * 5 = 100, 25 * 4 = 100, 50 * 2 = 100, dan 100 * 1 = 100. Secara logika, kita dapat menelusuri dengan menggunakan loop dari 1 hingga n, kemudian mengecek apakah bilangan yang ada pada loop habis dibagi n untuk menemukan faktor dari n. Jika diprogram dalam bahasa python, algoritma tersebut akan nampak seperti dibawah ini.

namun fungsi ini belum efisien, karena kita mencari dari 1 hingga n maka kita sebenarnya mengecek dua kali untuk angka yang sama, misalnya 2 * 5 = 10 dicek pada loop kedua, namun hasil tersebut dicek kembali pada loop kelima saat 5 * 2 = 10 dan akan berjalan sangat lama jika dipanggil dengan n yang bernilai besar. Algoritma diatas mempunyai Big-O sebesar O(n).

untuk mengoptimalkan fungsi mencari faktor, kita dapat mencari dengan loop hanya dari 1 sampai sqrt{n}. Jadi jika n = 100, maka kita akan hanya akan mencari dari 1 sampai 10 saja, dan faktor lainnya akan dicari dengan membagi n dengan bilangan yang ada pada loop. dengan begini Algoritma mempunyai Big-O sebesar O(sqrt{n}).

Sebagai perbandingan dari kedua fungsi tersebut, berikut merupakan program yang menghitung waktu yang digunakaan untuk mengeksekusi kedua fungsi tersebut.

Fungsi yang sudah dioptimalisasi membutuhkan waktu 0.13 detik untuk menyelesaikan eksekusi fungsi dengan n=600851475143, sedangkan fungsi pertama belum selesai eksekusi pada 302.89 detik (5 menit lebih) sdengan nilai n yang sama, sehingga harus dihentikan secara paksa.

link colab: https://colab.research.google.com/drive/1hsyvRV3Kxla_oMzTrF38WD63eoDBWTA8?usp=sharing