Kompleksitas Waktu untuk Algoritma Rekursif (Revisi)

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

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

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

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

        = dan seterusnya

n - i = 1

    -i = 1 - n

     i = n - 1

T(n) = 2ⁱT(n - i) + 2^i-1 + 2^i-2 + ..... + 2⁰

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

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

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

        = 2^n-1 + 2^n-1 - 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).