Menghitung Kompleksitas Waktu Asimptotik Nilai Maksimum dan Minimum

Nama : Manipan Alfanso Aritonang
NIM   : 153303030435
Fakustal Teknologi dan Informasi

Procedure Min Maks1 (input A : Tabel Int, n : integer, output min, maks : integer)

(Mencari nilai minimum dan maksimum di dalam tabel A yang berukuran n elemen, secara brute force.

Masukan: tabel A yang sudah terdefinisi elemen-elemennya

Keluaran: nilai maksimum dan nilai minimum tabel ).

Deklarasi

   i : integer

Algoritma:

       min ← Ai  ( inisialisasi nilai minimum )

       maks ← Ai  (inisialisasi nilai maksimum )

for i ←2 to n do

  if Ai  < min then

   min ← Ai

  endif

  if Ai  > maks then

   maks ← Ai

  endif

endfor

Hitung Kompleksitas Waktu Asimptotik. T(n) dari algoritma tersebut diatas

Jawab:

if i=j then { 1 elemen }

min←Ai

maks←Ai

else

if (i = j-1) then { 2 elemen }

if Ai < Aj then

maks←Aj

min←Ai

else

maks←Ai

min←Aj

endif

else { lebih dari 2 elemen }

k←(i+j) div 2 { bagidua tabel pada posisi k }

MinMaks2(A, i, k, min1, maks1)

MinMaks2(A, k+1, j, min2, maks2)

if min1 < min2 then

min←min1

else

min←min2

endif

if maks1<maks2 then

maks←maks2

else

maks←maks2

endif

Penyelesaian

Asumsi: n = 2k, dengan k bilangan bulat positif