Algoritma - Notasi Big O

Ketika anda ingin menjadi seorang programmer, kemampuan yang harus anda miliki adalah memprediksi jumlah sumber daya yang akan dihabiskan oleh kode yang anda buat dengan mengukur seberapa efisien algoritma yang telah ditulis. Inilah yang biasa dimaksud dengan Big O Notasi. Notasi ini diperkenalkan oleh Paul Bachmann, pertama kali di Jerman, pada tahun 1894.

photo/photo/office-working-app-computer-97077/

Notasi Big-O berfungsi dalam mengkategorikan algoritma ke fungsi yang menggambarkan upper limit atau batas atas dari pertumbuhan sebuah fungsi ketika masukan dari fungsi tersebut bertambah banyak dengan menggunakan fungsi Big-O. Disini nanti kompleksitas algoritma akan dinilai dengan Notasi Big O yang terdiri dari time complexity atau berapa lama algoritma itu jalan, space complexity atau berapa banyak memori yang bakal dipakai oleh algoritma.

Algoritma kadang melakukan jumlah operasi yang sama pada setiap kali pemanggilannya yang ternyata memerlukan waktu yang konstan. Selain itu ada juga algoritma lain yang melakukan jumlah operasi yang berbeda, tergantung dari jumlah input pada parameter seperti pemanggilan berurutan (sequence), maka dapat dipahami bahwa jumlah operasi yang dilakukannya tergantung dari jumlah pemanggilan. Dan disini harus memperhitungkan parameter yang nilainya mempengaruhi jumlah operasi yang dilakukan (problem size, kadang juga disebut input size)

Maka saat mengukur kompleksitas algoritma, bukan jumlah operasi yang tepat yang kita perlukan, namun bagaimana hubungan antara jumlah operasi tersebut dengan problem size-nya. Sehingga ketika ditemukan problem size-nya double, cari tahu apakah jumlah operasi akan tetap dua kali lipat atau akan bekembang dengan cara tertentu.

Pada algoritma yang memerlukan waktu yang konstan, melipatgandakan problem size tidak mempengaruhi jumlah operasi yang dilakukan. Apalagi ketika terdapat worst case atau kasus terburuk, yang maksudnya terdapat jumlah operasi terbanyak yang mungkin dilakukan oleh algoritma untuk problem size yang diberikan.

Notasi Big O bisa dicontohkan seperti :
  • O(1)
  • O(N)
  • O(N^2)
  • O(N^3)
  • O(sqrt(N))
  • O(log N)
  • O(N log N)
  • O(N!)
  • O(2^N)

Kecepatan program yang diinginkan seorang programmer adalah O(1) yang maksudnya bagaimanapun kompleksnya suatu program kecepatannya tetap sama yaitu O(1), Sedangkan O(N) kecepatannya lambat. O(N) maksudnya waktu yang diperlukan sebanding atau berbanding lurus dengan banyaknya data, simplenya ada data berjumlah 10 yang selesai dalam 1 detik misalnya, maka ketika datanya 100 biji selesainya dalam 10 detik, jadi waktu yang diperlukan 10 kali, beda dengan O(1) berapapun data input selesainya tetap 1 detik.

O(N^2) artinya kecepatan program menjadi N^2 atau berbanding parabolic, waktu yang diperlukan itu berbanding kuadrat dengan banyaknya data, artinya misal data sebanyak 10 selesai dalam 1 detik, maka data 100 selesai dalam 100 detik. ( data 10 menjadi data 100, maka 10 x lipat, waktu jadi 10*10 = 100 kali!).

Jadi Notasi Big O meng-capture tingkat pertumbuhan yang akhirnya terjadi, disini dia tidak akan peduli tentang konstanta. Maka di dunia big 0,atau dunia asymptotic, kita punya data 1 juta atau 1 saja itu sama saja.

1 = O(1)
10000000 = O(1), data 1 juta kali lipat tetap O(1).

Dan di dunia O besar, di dunia asimtotik, apakah kita memiliki satu juta atau satu, perbedaan yang sama. O besar persis sama. Jadi kami katakan satu juta adalah O besar (1). Jadi, perhatikan bahwa cara membaca kalimat, equal dan capital O kemudian braket adalah fungsi lain.

Cara membacanya adalah, sisi kiri adalah big O besar dari apa yang ada di dalam kurung itu. Dan di sini kita memiliki satu juta adalah big O (1). Dan contohnya inisiasi biaya (initialization costs), konstanta itu mungkin saja biaya inisialisasi ketika kita memulai program baru. Maka kita mungkin harus melakukan banyak pekerjaan yang sibuk di awal,tetapi pekerjaan yang sibuk itu sama, tidak peduli apa pun input kita.

langkah tidak berubah dengan ukuran input n

Dan bahkan jika itu satu juta langkah atau satu langkah yang tidak akan memberitahu kita bagaimana program itu berperilaku sebagai input yang semakin besar dan besar dan lebih besar dan jadi kita tidak perlu khawatir tentang hal itu. Sehingga kita menyatukan semuanya menjadi satu konstanta dan menganggap bahwa itu big O, tidak berubah sebagai perubahan N.

Kemudian pada analisis asimtotik, kita hanya peduli pada istilah dominant. Jadi kita hanya peduli tentang bagian perhitungan yang akan membuat dampak terbesar bagi hasil. Jadi kita hanya ingin mempertahankan bagian dari fungsi yang paling cepat berkembang. Misal:

3n + 3 = O(3n)

Sekarang perhatikan sistem operasi diatas, kita punya dua istilah di sini. Kita punya istilah 3n dan punya 3. Sekarang, 3n tumbuh saat n tumbuh. 3 tidak.Dan karena itu istilah dominan dari 2 bagian dari jumlah itu adalah 3n, dan dalam analisis big O, kita akan menyimpannya.

Jadi  3n + 3 adalah big O  (3n).
      3n + 3 = O(3n)

Tapi sekarang pikirkan kembali pengamatan kami sebelumnya, kami akan menjatuhkan konstanta dan 3n sama persis dengan n dalam big 0. Oke, jadi Anda punya dua prinsip ini.

Jadi semoga Anda bisa membandingkan dua fungsi yang berbeda berdasarkan asimtotik ini. Tetapi Anda mungkin bertanya-tanya, bagaimana kita dapat membuat pilihan-pilihan ini dan apa cara yang berprinsip untuk memahami analisis asimtotik?

f(n) = O(g(n))

artinya ada konstanta N dan c sehingga tiap n > N

f(n) ≤ C g(n)

Oke, jadi sekian dulu penjelasan singkat tentang notasi big O, saya mendorong Anda untuk tidak terlalu khawatir tentang definisi formal ini. Dan benar-benar pastikan bahwa Anda merasa nyaman dengan melihat kode dan mendapatkan asimtotik berdasarkan kode itu. Melihat melalui eksekusi dan benar-benar memilih big O untuk runtime kode.