Big
Oh
Big Oh adalah fungsi
yang berkaitan dengan kelajuan proses, dan biasanya digunakan dalam analisis
suatu algoritma untuk menentukan efisiensi dan kompleksitasnya.
-T(n) = O(f(n))
Bila ada suatu konstanta C, maka :
-T(n) ≤ C.(f(n))
Contoh Lain :
·
Jika
f(n) = 5n2 maka T(n) = O(n2)
·
Jika
f(n) = 7n2 + 3n + 5 maka T(n) = O(n2)
·
Jika f(n) = n3 – 2n + 8 maka
T(n) = O(n3)
Klasifikasi
Algoritma berdasarkan notasi Big Oh :
1.
T(n)
= c
Disebut sebagai algoritma konstan,
dimana programnya hanya dieksekusi dengan suatu nilai yang konstan. Bersifat
konstan dan tidak dipengaruhi parameter atau banyak ada yang dieksekusi.
Merupakan algoritma yang paling ideal.
Contoh Program Pascal :
Begin
A:=7;
End.
Maka T(n) = O(1), karena program
hanya dieksekusi satu kali, dan konstan.
2.
T(n)
= O(n)
Disebut algoritma linear, dimana
waktu eksekusinya sebanding dengan jumlah data, dan merupakan kondisi optimal
dalam membuat algoritma.
Contoh Program Pascal :
Begin
For I := 1 to n do
Begin
A:=A+1;
End;
End.
Maka T(n) = O(n) karena program
dieksekusi sejumlah n kali.
3.
T(n)
= O(n2)
Disebut algoritma kuadratik, karena
waktu eksekusi program akan sebanding dengan jumlah kuadrat jumlah data.
Biasanya timbul karena adanya nested loop
atau loop bersarang pada suatu program.
Contoh Program Pascal :
Begin
For I := 1 to n do
Begin
For
J:=1 to n do
Begin
A:=A+1;
End;
End;
End.
Loop dalam di eksekusi n kali. Loop
luar di eksekusi n kali. Oleh karena itu T(n) = O(n2) dan program di
eksekusi n x n atau n2.
4.
T(n)
= O(log n)
Disebut algoritma logaritmik,
karena waktu eksekusi sebanding dengan logaritma dari jumlah data. Biasanya
algoritma ini digunakan untuk memecahkan masalah besar menjadi masalah yang
lebih kecil.
Contoh : algoritma Binary Search
dan algoritma fungsi rekursif.
5.
T(n)
= O(n log n)
Disebut algoritma linearitmik,
karena merupakan gabungan dari linear dan logaritmik, biasanya digunakan untuk
memecahkan masalah yang besar menjadi masalah yang lebih kecil dan diselesaikan
secara terpisah, lalu kemudian hasilnya digabungkan.
Contoh : algoritma Quick Sort.
6.
T(n)
= O(n3)
Merupakan algoritma yang buruk dan
sebisa mungkin dihindari, biasanya algoritma ini dihasilkan dari 3 buah nested loop atau 3 buah loop bersarang.
Contoh program Pascal :
Begin
For I := 1 to n do
Begin
For
J:=1 to n do
Begin
For K:= 1 to n do
Begin
A:=A+1;
End;
End;
End;
End.
Loop terdalam di eksekusi n kali.
Loop tengah di eksekusi n kali. Loop luar di eksekusi n kali. Oleh karena itu
T(n) = O(n3) dan program di eksekusi n x n x n atau n3.
No comments:
Post a Comment