Analisis Algoritma

Sabtu, 22 Oktober 2016

BEST, WORST, dan AVERAGE

Untuk beberapa algoritma tertentu, kompleksitas waktu dibagi 3 :

- Best – case efficiency [Tmin (n)]
Kompleksitas dengan jumlah paling kecil.

- Worst – case efficiency [Tmax (n)]
Kompleksitas dengan jumlah paling besar.

- Average – case efficiency [Tavg (n)]
Kompleksitas dengan jumlah rata-rata keseluruhan kemungkinan.

Berikut ini beberapa contoh menghitung Tmax (n), Tmin (n), Tavg (n) :

1. Algoritma Mencari Elemen Max

procedure Mencari_Max(input a₁,...,a_n : integer, output max : integer)

Kamus:

i,j : integer

Algoritma:

max <-- a₁

j <-- 2

while (j <= n) do

if (a_j > max)

then

max <-- a_j

endif

i <-- i + 1

endwhile
enprocedure

2. Algoritma Ganjil Genap

ganjil_genap

Kamus:

bil, i,g1,g2,j1,j2,n : integer

rt1,rt2 : real

Algoritma:

write(“Masukkan Banyaknya Data = “)

input(n)

for i <-- 1 to n do

write('Bilangan ke:',i ,' ')

Input(bil)

if bil mod 2 = 0

then

j1 <-- j1 +1

g1 <-- g1+bil

else

j2 <-- j2+1

g2 <-- g2+bil

endif

endfor

rt1 <-- g1/j1

rt2 <-- g2/j2

write(“Jumlah bil. Ganjil= “)

write(“Jumlah bil. Genap= “)

write(“Rerata Ganjil= “)
write(“Rerata Genap= “)

3. Algoritma Binary Search

Procedure Binary_search(input a₁,...,a_n : integer, x : integer, output idx : integer)

Kamus:

i, j, k : integer

ketemu : boolean

Algoritma:

i <-- 1

j <-- n

ketemu <-- false

while ( i <= j) and (not ketemu)do

k <-- (i + j) div 2

if (a_k = x)

then

ketemu <-- true

else

if (a_k < x)

then

i <-- k + 1

else

j <-- k - 1

endif

endwhile

if (ketemu)

then

idx <-- k

else

idx <-- 0

endif
endprocedure

4. Algoritma Segitiga Piramida

Segitiga_Piramida

Deklarasi

n,kolom,I,j,m,c : integer

Algoritma

input(n)

kolom = (n*2)-1

for i <-- 1 to n do

for j <-- 1 to kolom do

m = j-n

if (m <= 0)

then

c <-- i + m

else

c <-- i – m

endif

if (c > 0)

then

output(“*”)

else

output(“ “)

endif

j <-- j+1

endfor

i <-- i + 1

endfor

5. Algoritma Faktorial

faktorial

Kamus:

i, n, x :integer

Algoritma:

input(n)

if (n<=0)

then

x <-- 1

else

x <-- 1

for i <-- 2 to n do

X <-- x*i

endfor

endif

output(x)

Baca selengkapnya

Selasa, 11 Oktober 2016

Menghitung Kompleksitas Waktu Algoritma T(n)

Rifaldi Yunus 08.48 1 Komentar

Rumus kompleksitas waktu eksekusi algoritma :

Contoh Menghitung kompleksitas waktu eksekusi algoritma :

1. Menghitung Energi Kinetik

Procedure Mengitung_energi_kinetik (output Ek : real)

Deklarasi :

massa,velocity : real

Algoritma :

input(massa)

input(velocity)

Ek <-- 0.5 * massa * velocity * velocity

Endprocedure

2. Menghitung Luas dan Volume Bola

Procedure Hitung_luas_dan_volume_bola (output luas,volume : real)

Deklarasi :

Jarijari : integer

Algoritma :

input (jarijari)

luas <-- 4 * 3.14 * jarijari * jarijari

volume <-- 1.33 * 3.14 * jarijari * jarijari * jarijari

Endprocedure

3. Konversi Bilangan Desimal ke Biner

Procedure konversi_bilangan_biner

Kamus :

des,desi : integer

bin : String

Algoritma :

//Memasukkan Suatu Bilangan Desimal

Input(des)

desi <-- des

bin <-- ' '

repeat

if(des mod 2 = 0)

then

bin <-- '0' + bin

else

bin <-- '1' + bin

endif

des <-- des div 2

until des = 0

Output('(',desi,') desimal =',bin,' (Biner)')

Endprocedure

C(n) : Input = 1

Output = 1

+ = 2n

Div = n

Mod = n

← = 3 + 2n

C_{op :}C_op Input = a

C_op Output = b

C_op + = c

C_op div = d

C_op mod = e

C_op <-- = f

T(n) = C_op * C(n)

T(n) = a + b + 2nc + nd + ne + (3+2n)f

4. Algoritma Fibonacci

Procedure Fibonaci (Input n : integer)

Kamus :

a,b,c,n,index : integer

Algoritma :

a <-- 0

b <-- 1

for index <-- 1 to n do

c <-- a+b

a <-- b

b <-- c

output(b)

endfor

Endprocedure

Time Efficiency T(n) :

Pengisian Nilai

n <-- 5 --> 1

a <-- 0 --> 1

b <-- 1 --> 1

c <-- a+b --> n

a <-- b --> n

b <-- c --> n

TOTAL --> 3+3n

Operasi Aritmatika

a + b --> n

TOTAL --> n

Keluaran

Output(b) --> n

TOTAL --> n

T(n) = C_op.C(n)

= (3+3n)D + (n)I + (n)A

5. Menghitung Faktorial

Procedure faktorial (input n : integer)

Kamus :

i, n, x :integer

Algoritma :

if (n<=0)

then

x <-- 1

else

x <-- 1

For i <-- 2 to n do

X <-- x*i

Endfor

Endif

Output(x)

Endprocedure

Time Efficiency T(n) :

Pengisian Nilai

x <-- 1 --> 2

x <-- x*i --> n-1

i <-- 2 to n --> n-1

TOTAL --> 2n

Operasi Aritmatika

x * i --> n-1

n <= 0 --> 1

n > 0 --> 1

TOTAL --> n + 1

Keluaran

Output(x) --> 1

TOTAL --> 1

T(n) = C_op.C(n)

= (2n)S + (n+1)I + (1)A

Baca selengkapnya

Selasa, 04 Oktober 2016

Geometric Problems

Rifaldi Yunus 08.40 Komentar

Geometric problems adalah masalah yang berkaitan dengan objek geometrik seperti titik, garis, poligon dan lain-lain.

Yunani Kuno : membangun geometrik sederhana contohnya segitiga, lingkaran dan lain-lain

Masakini: aplikasi komputer grafik, robot

Masalah klasik :

1. Problem closest pair

Masalah closest pair of points adalah masalah menentukan pasangan titik terdekat

atau pasangan titik yang mempunyai jarak minimal di antara pasangan titik yang lain

pada bidang dengan ruang dimensi tertentu. Salah satu cara menyelesaikan

permasalahan closest pair of points adalah dengan metode divide and conquer.

Menurut Weiss (1993), metode divide and conquer terdiri dua metode, yaitu:

divide : Membuat masalah menjadi bagian yang lebih kecil dengan membagi dua

permasalahan yang dilakukan secara berulang-ulang.

conquer : Penyelesaian masalah dari sub permasalahan yang ada.

Algoritma Divide and Conquer pada Ruang Dimensi Dua

Algoritma divide and conquer ini inputnya adalah titik sebanyak n sebagai anggota dari

himpunan S. Titik sebanyak n tersebut akan disortir oleh sumbu X kemudian disortir oleh sumbu

Y. Proses tersebut terjadi perulangan sampai diperoleh jarak minimal dari pasangan dua titik.

Langkah-langkah closest pair of points dengan algoritma divide and conquer pada ruang

dimensi dua adalah sebagai berikut:

Langkah 0 : Himpunan S sebagai input, yang terdiri dari n titik.

Langkah 1 : Menentukan garis vertikal m sebagai median, yang membagi

himpunan S menjadi S1 dan S2 menurut sumbu X.

Langkah 2 : Menentukan d1 dan closest pair of points dari d1 pada S1, dan menentukan d2 dan

closest pair of points dari d2 pada S2, dengan cara recursive.

Langkah 3 : d := min (d1,d2).

Langkah 4 : Membuat jarak d ke kanan dan ke kiri dari garis m yaitu (m-d,m] sebagai P1 dan

[m,m+d) sebagai P2.

Langkah 5 : Titik pada P1 dan P2 diproyeksikan pada garis m untuk disortir terhadap sumbu Y,

maka terbentuk P1* dan P2*.

Langkah 6 : Setiap titik pada P1* akan diperiksa oleh P2*secara recursive pada daerah persegi

d x 2d untuk mencari closest pair of points yang disebut d3.

Langkah 7 : ds:= min (d,d3).

2. Convex hull

Permasalahan convex hull adalah sebuah permasalahan yang memiliki aplikasi terapan yang

cukup banyak, seperti pada permasalahan grafika komputer, otomasi desain, pengenalan

pola (pattern recognition), dan penelitian operasi.

Algoritma untuk menyelesaikan permasalahan convex hull ada banyak cara misalnya

saja dengan pendekatan brute force, algoritma gift wrapping, algoritma Graham’s Scan,

dengan metode Divide and Conquer, dll.

Pemecahan Masalah Convex Hull denganAlgoritma Divide and Conquer

o Pertama-tama lakukan pengurutan terhadap titik-titik dari himpunan S yang

diberikan berdasarkan koordinat absis-X, dengan kompleksitas waktu O(n log n).

o Jika |S| ≤ 3, maka lakukan pencarian convex hull secara brute-force dengan

kompleksitas waktu O(1). (Basis)

o Jika tidak, partisi himpunan titik-titik pada S menjadi 2 buah himpunan A dan B,

dimana A terdiri dari setengah jumlah dari |S| dan titik dengan koordinat absix-X

yang terendah dan B terdiri dari setengah dari jumlah |S| dan titik dengan koordinat

absis-X terbesar

o Secara rekursif lakukan penghitungan terhadap HA = conv(A) dan HB = conv(B).

o Lakukan penggabungan (merge) terhadap kedua hull tersebut menjadi convex hull, H,

dengan menghitung dan mencari upper dan lower tangents untuk HA dan HB dengan

mengabaikan semua titik yang berada diantara dua buah tangen ini.

Sumber :

http://digilib.its.ac.id/ITS-paper-51121150006876/35427

http://dokumen.tips/documents/pengenalan-analisis-algoritma.html#

https://digilib.uns.ac.id/dokumen/download/6016/MTY3MTk=/Penyelesaian-masalah-closest-pair-of-points-pada-ruang-dimensi-dua-menggunakan-metode-divide-and-conquer-abstrak.pdf

informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2006.../MakalahSTMIK2007-125.pdf