Menentukan Worst Case, Best case, dan Average Case Suatu Algoritma

1. Algoritma Upah Karyawan

Program UpahKaryawan

Deklarasi

     nama : string

     JJK  : integer //Jumlah jam kerja

     lembur, upah : real

Algoritma

     input(nama,JJK)

     if JJK ≤ 48 then

           upah ← JJK*2000

     else

          lembur ← JJK-48

           upah ← 48*2000+lembur*3000

     endif

     output(nama,upah)

Analisis (worst case, best case, dan avarege case)

←

T_max(n)= n+3

T_min(n)= 3

T_avg(n)= 3+(n+3)
           2

       

2. Algoritma Menghitung Total Bayar

Program MenghitungTotalBayar

{ menghitung total bayar dari input kode barang, nama barang, harga  satuan, dan jumlah barang yang dibeli. }

Deklarasi

     kode, nama : string

jumlah : integer

     diskon, harga, harga_tot, total : real

Algoritma

     input(kode, nama, harga, jumlah)

     harga_tot ← harga * jumlah

     if jumlah ≥ 3 then

        diskon ← 0.125 * harga_tot

     else

        diskon ← 0

endif

     total ← harga_tot - diskon;

     output(total)

Analisis (worst case, best case, dan avarege case)

←

T_max(n)= 2 + n

T_min(n)= 2

T_avg(n)= 2+(2+n)
           2 

3. Algoritma Hitung Rata-rata

Program HitungRataRata2

{menghitung rata-rata dari sejumlah data bilangan bulat yang dibaca dari papan ketik selama data yang dibaca tidak sama dengan 0.}

Deklarasi

     x : integer     { data bilangan yang dibaca dari papan ketik } 

i : integer     { pencacah banyak data }  

     jumlah : integer     { pencatat jumlah data }

     rerata : real   { nilai rata-rata seluruh data }

Algoritma

     i ← 0           { inisialisasi pencatat banyak data dengan 0 }

     jumlah ← 0      { inisialisasi jumlah data dengan 0 }

     read(x)        

     while x ≠ 0 do       { lakukan penjumlahan selama x tidak nol }

           i ← i + 1             { naikkan pencatat banyaknya data }

           jumlah ← jumlah + x

           read(x)

     endwhile

     { x = 0 }

     If i ≠ 0 then   { data yang dibaca minimal 1 buah }

           rerata ← jumlah/i   

           write (rerata)

     else

           write (‘tidak ada data yang dimasukkan’)

     endif

Analisis (worst case, best case, dan avarege case)

←

T_max(n)= 3 + 2n ≈ n

T_min(n)= 5

T_avg(n)= 5+(3+2n) ≈ 2n ≈ n
            2

4. Algoritma Hitung Diskon

Program HitungDiskon

Deklarasi

harga, diskon, total : real

Algoritma
     input(harga)

if (harga > 300000)

then

diskon ← harga * 0.4

total ← harga - diskon

else

if (harga ≥ 150000) and (harga ≤ 300000)

then

diskon ← harga * 0.2

total ← harga - diskon

else

     diskon ← harga * 0.1

total ← harga - diskon

endif

endif

output(total)

Analisis (worst case, best case, dan avarege case)

←

T_max(n)= 2

T_min(n)= 2

T_avg(n)= 2

5. Algoritma Jenis Bilangan Bulat

Program JenisBilanganBulat

Deklarasi

     X : interger

Algoritma

     read (x)

     if x > 0 then

           write(‘positif’)

     else

           if x < 0 then

                write(‘negatif’)

           else

                if x = 0

                     write(‘nol’)

                endif

           endif

     endif

Analisis (worst case, best case, dan avarege case)

←

T_max(n)= n+2

T_min(n)= 2

T_avg(n)= 2+(n+2)
           2

          

refrensi :

1. https://danangjunaedi.files.wordpress.com/2011/08/sesi-14-kompleksitas-algoritma.pdf

2. Munir, Renaldi, Algoritma Pemrograman Dalam Bahasa Pascal dan C, 2011