Kompleksitas Komputasi
Big O Notation O(f(n))
Kompleksitas komputasi pada sebuah algoritma dibagi menjadi dua bagian, yaitu
●
Kompleksitas Waktu T(n)
●
Kompleksitas Ruang S(n)
Kompleksitas Waktu
diukur dari jumlah tahapan komputasi yang dibutuhkan untuk menjalankan algoritma sebagai fungsi dari ukuran masukan n
Kompleksitas Ruang
diukur dari memori yang digunakan oleh struktur data yang terdapat dalam algoritma sebagai fungsi dari ukuran masukan n
Pada saat melakukan pengukuran kompleksitas dari sebuah algoritma pada kompleksitas waktu, dapat dilakukan perkiraan salah satunya dengan menggunakan fungsi notasi Big O.
Notasi tersebut digunakan untuk menjelaskan dan menggambarkan tentang performansi terburuk yang berkaitan dengan jumlah permasalahan dari sebuah algoritma ketika jumlah data yang digunakan berjumlah sangat besar, dapat juga disebut sebagai asymtotic performance.
Lima aturan dasar yang digunakan untuk perhitungan algoritma dengan menggunakan notasi Big O
Pertama
Jika sebuah algoritma melakukan urutan langkah tertentu sebanyak f(N) kali untuk fungsi matematika f, maka dibutuhkan O(f(N)) langkah.
Contoh algoritma dalam pseudo-code Integer: FindLargest(Integer: array[]) Integer: largest = array[0] For i = 1 To
If (array[i] > largest) Then largest = array[i] Next i Return largest End FindLargest
Kedua Jika sebuah algoritma melakukan operasi yang membutuhkan O(f(N)) langkah dan kemudian melakukan operasi kedua yang membutuhkan O(g(N)) langkah untuk fungsi f dan g, maka total performansi algoritma tersebut adalah O(f(N)+g(N))
Contoh algoritma dalam pseudo-code Integer: FindLargest(Integer: array[]) Integer: largest = array[0] // O(1) For i = 1 To // O(N) If (array[i] > largest) Then largest = array[i] Next i Return largest // O(1) End FindLargest
Ketiga Jika sebuah algoritma melakukan operasi O(f(N)+g(N)) dan fungsi f(N) lebih besar dari fungsi g(N) dengan N dalam jumlah besar, maka algoritma tersebut dapat disederhanakan kedalam fungsi O(f(N))
Contoh algoritma dalam pseudo-code Integer: FindLargest(Integer: array[]) Integer: largest = array[0] // O(1) For i = 1 To // O(N) If (array[i] > largest) Then largest = array[i] Next i Return largest // O(1) End FindLargest
Keempat Jika sebuah algoritma melakukan operasi yang membutuhkan O(f(N)) langkah dan untuk setiap langkah pada operasi tersebut melakukan operasi lain sebesar O(g(N)) langkah, maka total performansi dari algoritma tersebut adalah O(f(N) x g(N))
Contoh algoritma dalam pseudo-code Boolean: ContainsDuplicates(Integer: array[]) For i = 0 To For j = 0 To If (i != j) Then If (array[i] == array[j]) Then Return True End If Next j Next i Return False End ContainsDuplicates
Kelima
Mengabaikan faktor pengali tetapan. Jika C adalah tetapan, O(C x f(N)) sama dengan O(f(N)) dan O(f(C x N)) sama dengan O(f(N))
Aturan-aturan tersebut terasa terlalu formal, dengan adanya f(N) dan g(N), tetapi dengan mudah dapat diterapkan. Selain aturan diatas, juga terdapat aturan yang sering digunakan untuk notasi Big O.
O(1) Algoritma dengan performansi O(1) membutuhkan jumlah waktu tetapan yang sama tidak perduli dengan seberapa besar data yang diolah. Algoritma ini cenderung untuk melakukan tugas yang relatif sepele karena tidak memiliki kemampuan untuk melihat seluruh input dalam satu waktu. Algoritma ini hanya melakukan sedikit langkah tetap denganperformansi sebesar O(1) dan waktu larian tidak bergantung kepada
Integer: DividingPoint(Integer: array[]) Integer: number1 = array[0] Integer: number2 = array[] Integer: number3 = array[ / 2] If () Return number1 If () Return number2 Return number3 End MiddleValue
O(Log N) Algoritma dengan performansi O(log N) secara umum
membagi
proses
kedalam
sejumlah
pecahan dengan bagian sama besar untuk setiap proses yang dilakukan. Salah satu contoh dari algoritma ini adalah algoritma binary tree. Pada algoritma binary tree, setiap simpul memiliki paling banyak dua cabang pada bagian kanan dan kiri
Node: FindItem(Integer: target_value) Node: test_node = Do Forever If (test_node == null) Return null If (target_value == test_node.Value) Then Return test_node Else If (target_value < test_node.Value) Then test_node = test_node.LeftChild Else test_node = test_node.RightChild End If End Do End FindItem
O(Sqrt N)
Beberapa
algoritma
memiliki
performansi
O(sqrt (N)) dengan sqrt adalah fungsi akar kuadrat. Algoritma dengan fungsi ini tidak umum digunakan. Fungsi ini tumbuh dengan sangat lambat tetapi lebih cepat dibandingkan dengan Log (N)
O(N) Algoritma
pada
aturan
pertama
untuk
penentuan Big O memiliki performansi O(N). Pertumbuhan algoritma fungsi N lebih cepat daripada log (N) dan sqrt (N) tetapi masih belum sangat cepat, Sebagian
besar
algoritma
performansi
O(N)
dapat
yang
memiliki
diimplementasikan
dengan baik pada saat dilakukan pengujian
O(N Log N) Misalkan sebuah algoritma melakukan proses ikal
terhadap
keseluruhan
butir
di
dalam
himpunan permasalahan kemudian melakukan proses ikal semacam proses kalkulasi O(log N) pada butir tersebut. Pada kasus ini, algoritma tersebut memiliki performansi O(N x log N) atau O(N log N)
O(N ) 2
Algoritma
yang
melakukan
proses
ikal
terhadap
keseluruhan masukan kemudian untuk setiap masukan melakukan proses ikal terhadap masukan kembali memiliki performansi O(N2). Selain dari performansi O(N2), terdapat performansi yang lain, yaitu O(N3) dan O(N4). O(N3) dan O(N4) lebih lambat daripada O(N2). Algoritma dapat juga dikatakan memiliki deret suku banyak jika melibatkan N, seperti O(N), O(N 2), O(N6), O(N4000)
O(2 ) N
Fungsi eksponensial 2 N mengalami pertumbuhan sangat
pesat,
sehingga
hanya
cocok
untuk
permasalahan berukuran kecil. Secara umum, algoritma ini digunakan untuk mencari seleksi masukan yang optimal. Untuk digunakan
permasalahan algoritma
eksponensial heuristik
yang
biasanya biasanya
memberikan hasil yang baik tetapi tidak memiliki jaminan memberikan hasil terbaik
O(N!) Fungsi faktorial (N!) didefinisikan untuk bilangan bulat lebih besar dari 0 yang dinyatakan dengan N! = 1 x 2 x3 x ... x N. Fungsi ini berkembang jauh lebih cepat daripada fungsi 2 N. Secara umum, algoritma dengan faktorial digunakan untuk mencari susunan optimal dari masukan. Salah satu contohnya adalah Traveling Salesman Problem (TSP). Pada permasalahan TSP, tujuannya adalah mencari rute dengan mengunjungi kota tepat satu kali dan kembali ke titik keberangkatan ketika meminimalisasikan jumlah jarak yang ditempuh
Tugas Mandiri Carilah Contoh Algoritma minimal 3 sesuai dengan Big O notation yang telah disebutkan sebelumnya. ● Buktikan dengan menggunakan analisis Big O Notation pada Kompleksitas Waktu dan Kompleksitas Ruang dengan mengukur waktu komputasi dengan input 1.000, 10.000, 100.000 dan 1.000.000 dan besar memori maksimal pada input tersebut dengan menggunakan screenshoot. ● Analisis dan jelaskan apabila hasil anda berbeda dengan hasil secara teoritis dan teman anda yang lainnya ●
Materi Selanjutnya
Latihan analisis Big O Notation pada Kompleksitas Waktu dan Kompleksitas Ruang
Terima Kasih
