TUGAS DESAIN ALGORITMA

Procedure MinMaks19input A: TabelInt, n : Integer,
{mencari nilai minimum dan maksimun di dalam table A yang berukura A n elemen
secara  brute force.

Masukkan Tabel A yang sudah terdefenisi elemen –elemen nya
Keluaran : nilai maksimum dan nilai table}

Deklarasi

  I : integer

Algoritma :
 min –A1 {Inisialisasi nilai minimum }
maks  –A1
for I – 2 to n do

                If A1 < min min then
                min A1
            endif

If A1 > maks then
   maks – A1
 endif

Endfor

JAWABAN :

Misalkan tabel A berisi elemen elemen sebagai berikut :

4          12        23        9          21        1          35        2          34

Ide dasar algoritma secara devide and conquer

4          12        23        9          21        1          35        2          34

                                        DEVIDE                      

4          12        23        9          21        1          35        2          34

4          12        23        9          21        1          35        2          34
            Min = 4                                                min=1
            maks =23                                 maks= 35

                               COMBINATE

4          12        23        9          21        1          35        2          34

Kompleksitas Waktu Asimplotik

T(n) = 2T (n/2)+2

Asumsi : n=2k dengan k bilangan bulat posistif , ,maka

T(n) = 2T(n/2)+2
                      =2(2T(N/4)+2) =4T(n/4)4+2
                      = 4T(2T(n/8)+2+4+2= 8T(n/8)+8+4+2
                      =0(n)