Analisa dan DesainAlgoritma

Tugas 2

Nama          : Johan
Fakultas      : Teknologi & Informasi Komputer
Universitas  : Prima Indonesia
Mata kuliah : Analisa dan Desain Algoritma

tugas 3 mencari notasi 2n-1
Soal_ mencari nilai minimum dan maksimum di dalam tabel A yang berukuran N elemen

Gampang Gampang susah klo ud cerita Algoritma, akann tetapi sesuatu yang sudah kita tau gak akan sulit lagi, yang terpenting dasar nya.

Procedure  MinMaks 1 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¬ A1        - inisialisasi nilai minimum
    maks¬A1       - 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 Asimpotik T(n) dari Algoritma diatas,?


 PENYELESAIAN


Jika  T(n) = (n – 1) + (n – 1) = 2n – 2  = O(n)
DIVIDE dan CONQUER:
4          12        23        9          21        1          35        2          24
4          12        23        9          21        1          35        2          24          
4          12        23        9          21        1          35        2          24

SOLVE dan COMBINE:

4          12        23        9          21        1          35                    2          24
min = 4            min = 9            min = 1            min = 35          min = 2
maks = 12        maks = 23        maks = 21        maks =35         maks = 24

4       12     23     9       21     1       35     2       24
min = 4                                    min = 1            min = 2
maks = 23                                maks = 21        maks = 35

4       12     23     9       21     1       35     2       24
min = 4                                    min = 1          
maks = 23                                maks = 35

4       12     23     9       21     1       5       2       24
min = 1
maks = 35

Maka,
Kompleksitas Waktu Asimptotik T(n) adalah :










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


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

 = 2k – 1 × 1 + 2k – 2
= n/2 + n – 2
= 3n/2  – 2          
= O(n)

terima kasih