Menghitung Waktu Eksekusi Suatu Algoritma

MENGHITUNG WAKTU EKSEKUSI SUATU ALGORITMA

CONTOH KASUS : MENGHITUNG PERPANGKATAN

PROGRAM Perpangkatan { Menghitung perpangkatan x^n , x sebagai bilangan bulat dan n ≥ 0 } DEKLARASI             x          : real                { Nilai yang dipangkatkan }             n          : integer          { Pemangkat }             hasil     : real                { Hasil pemangkatan }             i           : integer          { Pencacah pengulangan } ALGORITMA             Output (“ Menghitung Nilai Pemangkatan “)             Output (“ Masukkan Angka     : “)             Input    (x)             Output (“ Masukkan Pemangkat : “)             Input    (n)             hasil  <-- 1             For i <-- 1 to n do                         hasil <-- hasil * x             Endfor             Output (“Hasilnya Pemangkatan dari “,x,” pangkat “,n,” = “,hasil)

a.      Operasi Input

SINTAK	JUMLAH
Input    (x)	1
Input    (n)	1
TOTAL	2

b.      Operasi Output

SINTAK	JUMLAH
Output (“ Menghitung Nilai Pemangkatan “)	1
Output (“ Masukkan Angka     : “)	1
Output (“ Masukkan Pemangkat : “)	1
Output (“Hasilnya Pemangkatan dari “,x,” pangkat “,n,” = “,p)	1
TOTAL	4

c.      Operasi Pengisian Nilai

SINTAK	JUMLAH
hasil <-- 1	1
hasil <-- hasil * x	N
TOTAL	1+N

d.       Operasi Aritmatika

SINTAK	JUMLAH
hasil * x	1
TOTAL	1

Total kebutuhan waktu eksekusi algoritma Perpangkatan :

Total Waktu (t) = t1 + t2 + t3 + t4 = (2)a + (4)b +  (1 + N)c + d 

Sedangkan untuk–nya didapat dari Operasi Perkalian, yaitu :

hasil <-- hasil * x

Maka, kompleksitas waktu algoritma untuk algoritma Perpangkatan adalah :

Karena Operasi Perkalian dari  hasil <-- hasil * x  diulang sebanyak n ( pemangkatnya ).

Sumber Referensi :
Munir, Rinaldi, Algoritma & Pemprograman Dalam Bahasa Pascal dan C Edisi Revisi, Informatika, 2011.

Kompleksitas Algoritma, Ken Kinanti Purnamasari