Kompleksitas Komputasi Big O Notation O(f(n))
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)
diukur dari jumlah tahapan komputasi yang
dibutuhkan untuk menjalankan algoritma sebagai
fungsi dari ukuran masukan n
Kompleksitas Waktu
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
Jika sebuah algoritma melakukan urutan langkah
tertentu sebanyak f(N) kali untuk fungsi
matematika f, maka dibutuhkan O(f(N)) langkah.
Pertama
Contoh algoritma dalam pseudo-code
Integer: FindLargest(Integer: array[])
Integer: largest = array[0]
For i = 1 To <largest index>
If (array[i] > largest) Then largest = array[i]
Next i
Return largest
End FindLargest
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))
Kedua
Contoh algoritma dalam pseudo-code
Integer: FindLargest(Integer: array[])
Integer: largest = array[0] // O(1)
For i = 1 To <largest index> // O(N)
If (array[i] > largest) Then largest = array[i]
Next i
Return largest // O(1)
End FindLargest
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))
Ketiga
Contoh algoritma dalam pseudo-code
Integer: FindLargest(Integer: array[])
Integer: largest = array[0] // O(1)
For i = 1 To <largest index> // O(N)
If (array[i] > largest) Then largest = array[i]
Next i
Return largest // O(1)
End FindLargest
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))
Keempat
Contoh algoritma dalam pseudo-code
Boolean: ContainsDuplicates(Integer: array[])
For i = 0 To <largest index>
For j = 0 To <largest index>
If (i != j) Then
If (array[i] == array[j]) Then
Return True
End If
Next j
Next i
Return False
End ContainsDuplicates
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))
Kelima
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.
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
O(1)
Integer: DividingPoint(Integer: array[])
Integer: number1 = array[0]
Integer: number2 = array[<last index of array>]
Integer: number3 = array[<last index of array> / 2]
If (<number1 is between number2 and number3>)
Return number1
If (<number2 is between number1 and number3>)
Return number2
Return number3
End MiddleValue
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
O(Log N)
Node: FindItem(Integer: target_value)
Node: test_node = <root of tree>
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
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(Sqrt 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 yang memiliki
performansi O(N) dapat diimplementasikan
dengan baik pada saat dilakukan pengujian
O(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 Log N)
O(N2)
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(N2), O(N6),
O(N4000)
O(2N)
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 permasalahan eksponensial biasanya
digunakan algoritma heuristik yang 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