Rabu, 30 November 2016

,

Kompleksitas Waktu untuk Algoritma Rekursif (Revisi)

1 comment  
1. Algoritma Menghitung Faktorial
procedure faktorial(input x:integer output hasil:integer)
   if x = 1 then
      hasil ß 1
   else
      hasil ß faktorial(x-1)*x
   endif
endprocedure

Parameter Input : x
Operasi Dasar      : perkalian

Hasil = F(x) = F(x - 1) * x
             F(3) = F(3 - 1) * 3
                     = F(2) * 3
                     = F(1) * 2 *3
                     = 1 * 2 * 3
                     = 6

Relasi Rekurens :
T(n - 1) = T(n - 1 - 1) + 1
T(n - 1) = T(n - 2) + 1
T(n - 2) = T(n - 3) + 1
T(n - 3) = T(n - 4) + 1
             = dan seterusnya

T(n) = T(n - 1) + 1
        = T(n - 2) + 1 + 1
        = T(n - 3) + 1 + 1 + 1
        = dan seterusnya

n - i = 1
    -i = 1 - n
     i = n – 1

T(n) = T(n - i) + i
        = T(n - (n - 1)) + (n - 1)
        = T(n - n + 1) + (n - 1)
        = T(1) + (n - 1)
        = (n - 1)
        = n

Jadi, T(n) = n
         T(n) ∈ O(n)

2.Algoritma Menghitung Pangkat
Function pangkat(input x,y:integer):integer
   if y = 0 then
      pangkat ß 1
   else
      pangkat ß pangkat(x,y-1)*x
   endif
endfunction

Parameter Input : y
Operasi Dasar      : perkalian

Relasi Rekurens :
T(n - 1) = T(n - 1 - 1) + 1
T(n - 1) = T(n - 2) + 1
T(n - 2) = T(n - 3) + 1
T(n - 3) = T(n - 4) + 1
             = dan seterusnya

T(n) = T(n - 1) + 1
        = T(n - 2) + 1 + 1
        = T(n - 3) + 1 + 1 + 1
        = dan seterusnya

n - i = 0
    -i = - n
     i = n

T(n) = T(n - i) + i
        = T(n - n) + (n)
        = T(0) + (n)
        = n

Jadi, T(n) = n
         T(n) ∈ O(n)

3.Algoritma Menara Hanoi
Procedure hanoi(input n, A, B, C : integer)
Algoritma
   if n = 1 then
      write (‘Pindahkan piringan dari’,A,’ke’,B)
   else
      hanoi(n-1,A,C,B)
      write(‘Pindahkan piringan dari’,A,’ke’,B)
      hanoi(n-1,C,B,A)
   endif
endfunction

Parameter Input : n
Operasi Dasar      : pengurangan

Relasi Rekurens :
T(n)       = 2T(n - 1) + 1
T(n - 1) = 2T(n - 1 - 1) + 1
T(n - 1) = 2T(n - 2) + 1
T(n - 2) = 2T(n - 3) + 1
T(n - 3) = 2T(n - 4) + 1
              = dan seterusnya

T(n) = 2T(n - 1) + 1
        = 2(2T(n - 2) + 1) + 1
        = 22T(n - 2) + 2 + 1
        = 22(2T(n - 3) + 1) + 2 + 1
        = 23T(n – 3) + 22 + 2 + 1
        = dan seterusnya

n - i = 1
    -i = 1 - n
     i = n - 1

T(n) = 2iT(n - i) + 2i-1 + 2i-2 + ..... + 20
        = 2iT(n - i) + 2i - 1
        = 2n-1T(n - (n - 1)) + 2n-1 - 1
        = 2n-1 T(1) + 2n-1 - 1
        = 2n-1 + 2n-1 - 1
        = 2n - 1

Jadi, T(n) = 2n - 1
         T(n) ∈ O(2n)

Sumber :
http://eprints.undip.ac.id/18693/1/Pertemuan13-14.pdf
Desain & Analisis Algoritma – ZK Abdurahman Baizal
Munir, Renaldi. (2011). Algoritma & Pemrogramman Dalam Bahasa Pascal dan C. (edisi revisi).

Senin, 28 November 2016

,

Kompleksitas Waktu untuk Algoritma Rekursif

No comments  
KOMPLEKSITAS ALGORITMA : REKURSIF

1. Algoritma Menghitung Faktorial
Function faktorial(input n:integer):integer
   if n = 1 then
      faktorial ß 1
   else
      faktorial ß n*faktorial(n-1)
   endif
endfunction

Parameter Input : n
Operasi Dasar      : perkalian

Relasi Rekurens :
T(n) =       0                   , n = 0
T(n) = T(n-1)+1            , n > 0

Kompleksitas Waktu :
T(n) = T(n-1) + 1                                   substitusi         T(n-1) = T(n-2) + 1
        = [T(n-2) + 1] + 1 = T(n-2) + 2     substitusi         T(n-2) = T(n-3) + 1
        = [T(n-3) + 2] + 1 = T(n-3) + 3
        = .....
        = T(0) + n
        = 0 + n
Jadi, T(n) = n
         T(n) ∈ O(n)

2.Algoritma Menghitung Pangkat
Function pangkat(input x,y:integer):integer
   if y = 0 then
      pangkat ß 1
   else
      pangkat ß pangkat(x,y-1)*x
   endif

endfunction

Parameter Input : n
Operasi Dasar      : =

Relasi Rekurens :
T(n) =       0                   , n = 0
T(n) = T(n-1)+1            , n > 0

Kompleksitas Waktu :
T(n) = T(n-1) + 1                                   substitusi         T(n-1) = T(n-2) + 1
        = [T(n-2) + 1] + 1 = T(n-2) + 2     substitusi         T(n-2) = T(n-3) + 1
        = [T(n-3) + 2] + 1 = T(n-3) + 3
        = .....
        = T(0) + n
        = 0 + n
Jadi, T(n) = n
         T(n) ∈ O(n)

3.Algoritma Menara Hanoi
Procedure hanoi(input n, A, B, C : integer)
Algoritma
   if n = 1 then
      write (‘Pindahkan piringan dari’,A,’ke’,B)
   else
      hanoi(n-1,A,C,B)
      write(‘Pindahkan piringan dari’,A,’ke’,B)
      hanoi(n-1,C,B,A)
   endif
endfunction

Relasi Rekurens :
T(n) =       1                  , n = 1
T(n) = 2T(n-1)+1          , n > 1

Kompleksitas Waktu :
T(n) = 1 + 2T(n-1)
        = 1 + 2(1 + 2T(n - 2)) = 1 + 2 + 22T(n - 2)
        = 1 + 2 + 22 (1 + 2T(n - 3)) = 1 + 2 + 22 + 23T(n - 3)
        = .....
        = (1 +2 + 22 + ..... + 2n-2) + 2n-1T(1)
        = 1 + 2 + 22 + ..... + 2n-2.1
        = 2n - 1
Jadi, T(n) = 2n – 1
         T(n) ∈ O(2n)


Sumber :
http://eprints.undip.ac.id/18693/1/Pertemuan13-14.pdf
Desain & Analisis Algoritma – ZK Abdurahman Baizal
Munir, Renaldi. (2011). Algoritma & Pemrogramman Dalam Bahasa Pascal dan C. (edisi revisi).