R. A. Algoritma Univ Trunojoyo
ª
Algoritma yang bagus adalah algoritma yang mangkus. Kemangkusan algoritma
diukur dari berapa jumlah waktu dan ruang (space) memori yang dibutuhkan untuk
menjalankannya. Algoritma yang mangkus ialah algoritma yang meminimumkan kebutuhan
waktu dan ruang.
ª
Model perhitungan waktu dan ruang. Contoh:
Jumlah<-0
k<-1
while k<=n do
jumlah<-jumlah+a(k)
k<-k+1
endwhile
r<-jumlah/n
§
operasi pengisian nilai (jumlah<-0, k<-1, jumlah<-jumlah+a(k),
k<-k+1 dan r<-jumlah/n) jumlah seluruh pengisian nilainya adalah
t(1)=1+1+n+n+1=3+2n
§
operasi penjumlahan (jumlah+a(k) dan k+1) jumlah seuruh operasi penjumlahan
adalah t(2)=n+n=2n
§
operasi pembagian (jumlah/n) jumlah seluruh operasi pembagian adalah t(3)=1
§
total kebutuhan waktu algoritma HitungRerata: t=t(1)+t(2)+t(3)=(3+2n)a+2nb+c
detik
ª
Besaran yang dipakai untuk menerangkan model abstrak pengukuran waktu/ruang
ini adalah kompleksitas algoritma. Ada dua macam kompleksitas algoritma, yaitu:
kompleksitas waktu dan kompleksitas ruang.
§
Kompleksitas waktu, T(n), diukur dari jumlah tahapan komputasi yang
dibutuhkan untuk menjalankan algoritma sebagai fungsi dari ukuran masukan n (Tmax(n)
= worst case, Ymin(n) = best case dan Tavg(n) = average
case). Contoh:
i ← 0
while i < n and A[ i ] ≠ K do
i ← i + 1
if i < n return i
else return -1
¨
Cworst
(n) = n
¨
Cbest
(n) = 1
Average-case
efficiency
Asumsi standar:
Probabilitas dari pencarian
yang sukses adalah p (0 ≤ p ≤ 1).
Probabilitas dari pencocokan
pertama yang muncul pada posisi ke i dari list adalah sama untuk setiap i.
Analisa efisiensi waktu
sequential search:
Cavg (n) = [ 1.p/n
+ 2.p/n + … + i.p/n + … + n.p/n ] + n.(1-p )
= p/n [1+2+…+i
+ … + n ] + n(1-p )
= p/n . n . (n+1)/ 2 + n(1-p)
= p(n+1)/ 2 + n(1- p)
¨
Notasi “O”
disebut notasi “O-Besar” (Big-O) yang merupakan notasi kompleksitas waktu asimptotik.
¨
Definisi: T(n)
£ C(f (n))
¨
f(n) adalah
batas lebih atas (upper bound) dari T(n)
untuk n yang besar.
Contoh
4. Tunjukkan bahwa T(n)
= 3n + 2 = O(n).
Penyelesaian:
3n + 2 = O(n)
karena
3n + 2 £ 3n+2n = 5n
untuk semua n ³ 1 (C = 5 dan n0 = 1).
Contoh
5. Tunjukkan bahwa T(n)
= 2n2 + 6n + 1 = O(n2).
Penyelesaian:
2n2 + 6n + 1 = O(n2) karena
2n2 + 6n + 1 £ 2n2 + 6n2 + n2 = 9n2
untuk semua n ³ 1 (C =9 dan n0 = 1).
(a) T1(n) + T2(n) = O(f(n))
+ O(g(n)) = O(max(f(n), g(n))
(b) T1(n)T2(n) = O(f(n))O(g(n)) = O(f(n)g(n))
(c) O(cf(n))
= O(f(n)), c adalah konstanta
(d) f(n) = O(f(n))
Contoh:
read(x); O(1)
x:=x+a[k]; O(1) + O(1) +
O(1) = O(1)
writeln(x); O(1)
maka
Kompleksitas waktu
asimptotik = O(1) + O(1) + O(1) = O(1)
Penjelasan: O(1) + O(1) + O(1) = O(max(1,1)) + O(1) = O(1) + O(1) = O(max(1,1)) = O(1)
contoh:
read(x); O(1)
if x mod 2=0 then O(1)
begin
x:=x+1; O(1)
writeln(x); O(1)
end
else
writeln(x); O(1)
maka
Kompleksitas waktu
asimptotik:
= O(1) + O(1) + max(O(1)+O(1), O(1))
= O(1) + max(O(1),O(1))
= O(1) + O(1)
= O(1)
Contoh:
for i:=1 to n do
jumlah:=jumlah+a[i]; O(1)
maka
Kompleksitas waktu
asimptotik = n . O(1)
= O(n .1)=O(n)
Contoh:
for i:=1 to n do
for j:=1 to n do
a[i,j]:=0; O(1)
maka
nO(n) = O(n.n) = O(n2)
jumlah pengulangan
seluruhnya = 1 + 2 + … + n = n(n
+ 1)/2
kompleksitas waktu
asimptotik = n(n + 1)/2 .O(1)
contoh:
i:=2; O(1)
while
i <= n do O(1)
begin
jumlah:=jumlah + a[i]; O(1)
i:=i+1; O(1)
end;
maka
Kompleksitas waktu
asimptotiknya adalah
= O(1) +
(n-1) { O(1) + O(1) + O(1) }
= O(1) + (n-1) O(1)
= O(1) + O(n-1)
= O(1) + O(n)
= O(n)
Kelompok
Algoritma
|
Nama
|
O(1)
O(log n)
O(n)
O(n log n)
O(n2)
O(n3)
O(2n)
O(n!)
|
konstan
logaritmik
lanjar
n log n
kuadratik
kubik
eksponensial
faktorial
|
§
Kompleksitas ruang, S(n), diukur dari memori yang digunakan oleh struktur
data yang terdapat di dalam algoritma sebagai fungsi dari ukuran masukan n.
ª
Note:
§
Buat definisi binary search (contoh), algoritmanya dalam bentuk pseudocode,
tentukan worst case, best case, average case.
§
Buat definisi selection sort (contoh), algoritmanya dalam bentuk
pseudocode, tentukan worst case, best case, average case.
Jawab:
§
Soal nomer 1:
Algorithm BinarySearch(A[0..n-1], K)
l ← 0; r ← n -1
while l ≤r do
m ←└(l+r)/2┘
if K = A[m] return m
else if K < A[m] r←m-1
else l←m+1
return -1
§
Soal moner 2:
Algorithm SelectionSort (A[0 .. n – 1])
for i ¬ 0 to n – 2 do
min ¬ i
for j ¬ i+1 to n – 1 do
if A[j] < A[min]
min ¬ j
swap A[i] and
A[min]
ª
Algoritma
brute force memecahkan masalah dengan sangat sederhana, langsung dan
dengan cara yang jelas (obvious way).
ª
Contoh
brute force:
§
Menghitung an (a > 0, n
adalah bilangan bulat tak-negatif)
§
Menghitung n! (n bilangan bulat
tak-negatif)
§
Mengalikan dua buah matrik yang berukuran n ×
n.
procedure PerkalianMatriks(input A, B : Matriks,
input n : integer,
output C :
Matriks)
|
Deklarasi
i, j, k : integer
|
Algoritma
for i¬1 to n do
for
j¬1 to n do
C[i,j]¬0 {
inisialisasi penjumlah }
for k ¬ 1 to n do
C[i,j]¬C[i,j] + A[i,k]*B[k,j]
endfor
endfor
endfor
|
Kompleksitas = O(n)
§
Menemukan semua faktor dari bilangan bulat n
selain dari 1 dan n itu sendiri.
procedure CariFaktor(input n : integer)
Deklarasi
k : integer
Algoritma:
k¬1
ketemu ¬ false
for k¬2 to n - 1 do
if n mod k =
0 then
write(k)
endif
endfor
§
Sequential
Search
procedure
PencarianBeruntun(input a1, a2, ..., an
: integer, x : integer, output idx : integer)
Deklarasi
k : integer
Algoritma:
k¬1
while (k < n) and (ak
¹ x) do
k ¬ k + 1
endwhile
{ k = n or ak = x }
if ak = x then { x ditemukan }
idx¬k
else
idx¬ 0 { x tidak ditemukan }
endif
§
Bubble
Sort
procedure BubbleSort (input/output L :
TabelInt, input n : integer)
|
Deklarasi
i : integer
k : integer
temp : integer
|
Algoritma:
for i ¬ 1 to n - 1 do
for k ¬ n downto
i + 1 do
if L[k] < L[k-1] then
temp ¬
L[k]
L[k] ¬ L[k-1]
L[k-1] ¬ temp
endif
endfor
endfor
|
Kompleksitas = O(n2)
ª
Algoritma
brute force umumnya tidak “cerdas” dan tidak mangkus, karena ia
membutuhkan jumlah langkah yang besar dalam penyelesaiannya. Kadang-kadang
algoritma brute force disebut juga algoritma naif (naïve algorithm). Contoh:
§
Pencocokan
string (string matching)
Pattern: NOT
Teks: NOBODY NOTICED HIM
NOBODY NOTICED
HIM
1 NOT
2 NOT
3 NOT
4 NOT
5 NOT
6 NOT
7 NOT
8 NOT
procedure PencocokanString(input
P : string, T : string, n, m : integer, output idx
: integer)
Deklarasi
i : integer
ketemu
: boolean
Algoritma:
i¬0
ketemu¬false
while (i £ n-m) and (not
ketemu) do
j¬1
while (j £ m) and (Pj
= Ti+j ) do
j¬j+1
endwhile
{ j
> m or Pj ¹ Ti+j
}
if j = m then
ketemu¬true
Kompleksitas algoritma: O(nm)
pada kasus terburuk
O(n)
pada kasus rata-rata.
§
Mencari Pasangan Titik yang Jaraknya Terdekat
procedure CariDuaTitikTerdekat(input P : SetOfPoint, n : integer, output
P1, P2 : Point)
Deklarasi
d, dmin : real
i,
j : integer
Algoritma:
dmin¬9999
for i¬1 to
n-1 do
for j¬i+1 to
n do
d¬Ö((Pi.x-Pj.x)2
+ ((Pi.y-Pj.y)2)
if d < dmin then
dmin¬d
P1¬Pi
P2¬Pj
endif
endfor
endfor
kompleksitas algoritma = O(n2)
ª
Kelebihan metode brute force:
§
Metode brute
force dapat digunakan untuk memecahkan hampir sebagian besar masalah (wide
applicability).
§
Metode brute force sederhana dan mudah dimengerti.
§
Metode brute force menghasilkan algoritma yang layak untuk beberapa
masalah penting seperti pencarian, pengurutan, pencocokan string,
perkalian matriks.
§
Metode brute force menghasilkan algoritma baku (standard) untuk
tugas-tugas komputasi seperti penjumlahan/perkalian n buah bilangan,
menentukan elemen minimum atau maksimum di dalam tabel (list).
ª
Kelemahan metode brute force:
§
Metode brute force jarang menghasilkan algoritma yang mangkus.
§
Beberapa algoritma brute force lambat sehingga tidak dapat diterima.
§
Tidak sekontruktif/sekreatif teknik
pemecahan masalah lainnya.
ª
Exhaustive search adalah teknik pencarian solusi secara solusi brute force
untuk masalah yang melibatkan pencarian elemen dengan sifat khusus. Contoh:
§
Travelling Salesperson Problem
(TSP): Persoalan TSP tidak lain adalah menemukan sirkuit Hamilton dengan
bobot minimum.
§
Knapsack: Bagaimana memilih objek-objek yang dimasukkan ke dalam knapsack
sedemikian sehingga memaksimumkan keuntungan. Total bobot objek yang dimasukkan
ke dalam knapsack tidak boleh melebihi kapasitas knapsack.
Himpunan Bagian
|
Total Bobot
|
Total keuntungan
|
{}
{1}
{2}
{3}
{4}
{1, 2}
{1, 3}
{1, 4}
{2, 3}
{2, 4}
{3, 4}
{1, 2, 3}
{1, 2, 4}
{1, 3, 4}
{2, 3, 4}
{1, 2, 3, 4}
|
0
2
5
10
5
7
12
7
15
10
15
17
12
17
20
22
|
0
20
30
50
10
50
70
30
80
40
60
tidak layak
60
tidak layak
tidak layak
tidak layak
|
Himpunan bagian objek yang memberikan keuntungan
maksimum adalah {2, 3} dengan total keuntungan adalah 80. Solusi: X = {0, 1, 1, 0}
ª
Exhaustive Search dalam Bidang Kriptografi: Di dalam bidang
kriptografi, exhaustive search merupakan
teknik yang digunakan penyerang untuk menemukan kunci enkripsi dengan
cara mencoba semua kemungkinan kunci. Serangan semacam ini dikenal dengan nama
exhaustive key search attack atau brute force attack. Contoh: Panjang kunci
enkripsi pada algoritma DES (Data Encryption Standard) = 64 bit. Dari 64 bit
tersebut, hanya 56 bit yang digunakan (8 bit paritas lainnya tidak dipakai).
Jumlah kombinasi kunci yang harus dievaluasi oleh pihak lawan adalah sebanyak
(2)(2)(2)(2)(2) … (2)(2) = 256 = 7.205.759.403.7927.936
ª
Mempercepat Algoritma Exhaustive Search: Salah satu teknik yang digunakan
untuk mempercepat pencarian solusi adalah teknik heuristik (heuristic). Contoh:
Contoh: Masalah anagram. Anagram adalah penukaran huruf dalam sebuah kata atau
kalimat sehingga kata atau kalimat yang baru mempunyai arti lain.
Contoh-contoh anagram (semua
contoh dalam Bahasa Inggris):
lived => devil; tea => eat; charm => march
ª
Divide
and Conquer dulunya adalah strategi militer yang dikenal dengan nama divide ut
imperes. Sekarang strategi tersebut
menjadi strategi fundamental di dalam ilmu komputer dengan nama Divide
and Conquer.
ª
Divide:
membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan
masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama),
Conquer: memecahkan (menyelesaikan) masing-masing upa-masalah (secara rekursif), dan Combine: mengabungkan solusi
masing-masing upa-masalah sehingga membentuk solusi masalah semula.
procedure DIVIDE_and_CONQUER(input n : integer)
Deklarasi
r, k : integer
Algoritma
if n £ n0 then
SOLVE upa-masalah yang berukuran n ini
else
Bagi menjadi r upa-masalah, masing-masing
berukuran n/k
for masing-masing dari r
upa-masalah do
DIVIDE_and_CONQUER(n/k)
endfor
COMBINE solusi dari r upa-masalah menjadi solusi masalah semula}
Endif
Jika pembagian selalu menghasilkan dua
upa-masalah yang berukuran sama:
procedure DIVIDE_and_CONQUER(input n : integer)
Deklarasi
r, k : integer
Algoritma
if n £ n0 then
SOLVE upa-masalah yang berukuran n ini
else
Bagi menjadi 2 upa-masalah, masing-masing
berukuran n/2
DIVIDE_and_CONQUER(upa-masalah pertama yang berukuran
n/2)
DIVIDE_and_CONQUER(upa-masalah kedua yang
berukuran n/2)
COMBINE solusi dari 2 upa-masalah
Endif
Contoh: Mencari nilai maksimum dan
nilai minimum
procedure MinMaks1(input A :
TabelInt, n : integer, output min, maks : integer)
Deklarasi
i : integer
Algoritma:
min¬ A1
maks¬A1
for
i¬2 to n do
if
Ai < min then
min¬Ai
endif
if
Ai > maks then
maks¬Ai
endif
endfor
T(n) = (n – 1) + (n
– 1) = 2n – 2 = O(n)
a
gan, boleh tau contoh kasus untuk tiap O(1), O(log n), O(n), O(n log n), O(n2), O(n3), O(2n), O(n!)?
ReplyDeletemisal O(1) bisa di pakai pada program apa gt. mohon sangat bantuannya gan. terimakasih
ini blog apaan bro? gajelas sama sekali
ReplyDelete