Kompleksitas Waktu untuk Algoritma Rekursif

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 + 2²T(n - 2)

        = 1 + 2 + 2² (1 + 2T(n - 3)) = 1 + 2 + 2² + 2³T(n - 3)

        = .....

        = (1 +2 + 2² + ..... + 2^n-2) + 2^n-1T(1)

        = 1 + 2 + 2² + ..... + 2^n-2.1

        = 2ⁿ - 1

Jadi, T(n) = 2ⁿ – 1

         T(n) ∈ O(2ⁿ)

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).