Tugas Slide 24

  1. Buat algoritma untuk menghitung Xn secara iteratif menggunakan cara Xn = X * X * X * … * X sebanyak n kali.
  2. Estimasi running time algoritma yang anda buat

 

Jawab :

 

Algoritma pangkat (X,n)

If    n = 1

return X

else

   return (X * pangkat(X, n-1))

Estimasi Waktu

1)      Input = n

2)      Menentukan basic operation

If  n=1

3)      Menentukan best case, average case, dan worst case :

Untuk input sejumlah n , pohon rekursinya selalu sama. Sehingga tidak ada best case, average case maupun worst case.

4)      Menentukan rumus sigma untuk menunjukkan berapa kali basic operation dieksekusi.

C(n)         : menyatakan banyaknya basic operation dieksekusi untuk input berukuran n

C(n-1)     : menyatakan banyaknya basic operation dieksekusi untuk input

berukuran n-1

 

Mensubstitusikan kedua persamaan di atas :

C(n) = C(n-1) +1 , untuk n > 1 rekursif case

C(1) = 1 , best case

 

Mencari persamaan recursive dari C(n) :

C(n) = C(n – 1) + 1

C(n) = (C(n – 2) + 1) + 1 = C(n) = C(n – 2) + 2

C(n) = (C(n – 3) + 1) + 2 = C(n) = C(n – 3) + 3

C(n) = (C(n – 4) + 1) + 3 = C(n) = C(n – 4) + 4, dst

 

Pola umum :

C(n) = C(n-i)+i

 

Nilai initial condition  C(1) disubtitusikan ke C(n – i) pada bentuk umum C(n).

C(n) = C(n – i) + i

C(n) = C(1) + i

C(n) = i + 1

 

Rumus sigma :

5)      Menyelesaikan rumus sigma untuk mendapatkan perhitungan berapa kali basic operation dieksekusi

C(n) = i + 1

Subtitusi tersebut ditulis C(n – i) = C(1) atau

n – i = 1

i = n – 1

nilai i = n – 1 disubtitusikan ke bentuk umum

C(n) = i + 1 sehingga

C(n) = n – 1 + 1

C(n) = n

 

Sehingga untuk ukuran n, maka basic operation dilakukan sebanyak n kali.

T(n) = Cop * C(n)

T(n) = 1 * n

T(n) = n

 

Tugas 2  Slide 27 , Algoritma Mystery

Algorithm mystery(A[0..n-1])

  1. X ← A[0]
  2. for i ← 1 to n – 1 do
  3.             if A[i] > X
  4.                         X ← A[i]
  5. return X

 

Soal :

  1. Apa yang dilakukan algoritma mystery?

Mencari nilai integer terbesar dari array A

 

  1. Estimasikan waktu eksekusi algoritma mystery

1)   Menentukan parameter yang mengindikasikan ukuran input : n

karena jika nilai n makin besar maka banyaknya eksekusi loop bertambah .Untuk algoritma mystery , parameter ukuran inputnya adalah banyaknya elemen array(n)

2)   Identifikasi basic operation loop

for i ← 1 to n – 1

3)   Menentukan apakah untuk ukuran input yang sama banyaknya eksekusi basic operation bisa berbeda .

Untuk input n tertentu , recursion treenya selalu sama. Sehingga tidak ada best case, average case maupun worst case.

4)   Menentukan rumus sigma berapa kali basic operation di eksekusi

 

 

5)      Menyelesaikan rumus sigma yang menunjukkan berapa kali basic operation dieksekusi

T(n) = Cop * C(n)

T(n) = 1 * n-1

T(n) = n-1

 

  1. Estimasi waktu eksekusi algoritma mystery untuk input A = [1, 2, 5, 9, 4, 4, 7, 10, 1, 6]

Algorithm mystery (A[0..n-1])

  1. X := 1
  2. For I =1 ,2,3,4,5,6,7,8,9
  3.       If  A[1] > 1                 //true 2>1
  4.                   X = 2
  5.       If A[2] > 2                  // true 5 >2
  6.                   X = 5
  7.       If A[3] > 5                   // true 9 > 5
  8.                   X = 9
  9.       If  A[4] >  9                // false 4 < 9
  10.       If  A[5] > 9                 // false 4 < 9
  11.       If  A[6] > 9                 // false 7 < 9
  12.       If  A[7] > 9                 // true 10 > 9
  13.                   X = 10
  14.       If A[8] >  10               // false 1<10
  15.       If A[9] > 10                //false 6<10
  16. Return X                           // X=10

Estimasi waktu eksekusi :

T(n) = n-1

T(10) = 9

 

Tugas Slide 29

  • Algoritma mystery T(n) = n – 1. Estimasi waktu eksekusi algoritma jika array inputnya memiliki anggota
    •   10 elemen

T(10) = 9

  •   20 elemen

T(20) =1 9

  •   30 elemen

T(30) = 29

  • Buat grafik yang menunjukkan hubungan antara banyaknya elemen array yang dieksekusi dengan waktu eksekusi

Grafik linear

 

 

 

 

 

 

Tugas Slide 38

Tentukan kelas orders of growth dari

  1. T1(n) = 2n3 + 4n + 1                                  : OOG nya cubic

OOG T(n) = n3

        Bila n nya dinaikkan 2 kali semula maka waktu pelaksanaan algoritma meningkat menjadi delapan kali semula

  1. 2.        T2(n) = 0,5 n! + n10                                                               

Saat n < 15 OoG n10

Bila n dijadikan 2 kali semula maka waktu pelaksanaan algoritma menjadi 1024 kali semula

Saat n >= 15 OoG n!

                Bila n dijadikan dua kali semula maka waktu pelaksanaan algoritma menjadi factorial dari 2n

  1. T3(n) = n3 + n logn

Bila n nya dinaikkan 2 kali semula maka waktu pelaksanaan algoritma meningkat menjadi delapan kali semula

  1. T4(n) = 2n + 4n3 + logn +10

Saat n <14 maka OoG yang mempengaruhi 4n3  yaitu class cubic

Bila n nya dinaikkan 2 kali semula maka waktu pelaksanaan algoritma meningkat menjadi delapan kali semula

Saat n > 14 maka OoG yang mempengaruhi 2n yaitu pada class exponential

Bila n dijadikan dua kali semula maka waktu pelaksanaan algoritma menjadi kuadrat kali semula