Kompleksitas Algoritma Rekursif (Revisi)

1. Contoh kasus bilangan fibonacci

    function Fibonacci (input n : integer) → integer;

    Algoritma :  

if (n=0) then

                  Fibonacci ← 0

                else if  (n = 1) then

                          Fibonacci ← 1

                       else

                           Fibonacci ← Fibonacci  (n-1) + Fibonacci  (n-2)

                        endif

                endif

    endfunction

    
    Operasi dasar utama : +

    Rekurens : Fibonacci  (n-1) + Fibonacci  (n-2) 
                 
          misal :  T(2) = Fibonacci(2-1) + Fibonacci(2-2)
                             = Fibonacci(1)
                      T(2) = 1

    Penghenti : T(1) = 0
     

    Permisalan :

    T(n-1) = T(n-1) + T(n-2) + 1                                            T(n-i) → T(1)
    T(n-2) = T(n-2) + T(n-3) + 1                                                 n-i = 1

    T(n-3) = T(n-3) + T(n-4) + 1                                                   -i = 1-n
                                                                                                     i = n-1
    Sehingga ,
    T(n) = T(n-1) + T(n-2) + 1
            = T(n-2) + T(n-3) + 1 + 1
            = T(n-3) + T(n-4) + 1 + 1 + 1
            = T(n-4) + T(n-5) + 1 + 1 + 1 + 1

    T(n) = T(n-i) + T(n-i-1) + i
            = T(n-(n-i)) + T(n-(n-1-1)) + (n-1)
            = T(n-n+1) + T(n-n+2) + (n-1)
            = T(1) + T(2) + (n-1)
            = 0 + 1 + (n-1)
            = 1 + (n-1) ∈ O(n)

    

2. Contoh kasus perpangkatan dimana aⁿ (a bilangan bulat dan n > 0)

    function Pangkat (input a, n : integer) → integer

    Algoritma :

                if n = 0 then

                return 1

              else

                  return a * Pangkat(a, n-1)

              endif  

    endfunction

    Operasi dasar utama : -
    Rekurens : Pangkat(n-1)
    Penghenti : T(1) = 0

    Permisalan :

    T(n-1) = T(n-1) + 1                                            T(n-i) → T(1)
    T(n-2) = T(n-2) + 1                                                 n-i = 1
    T(n-3) = T(n-3) + 1                                                   -i = 1-n
                                                                                       i = n-1
     Sehingga,
     T(n) = T(n-1)  + 1
            = T(n-2)  + 1 + 1
            = T(n-3)  + 1 + 1 + 1


     T(n) = T(n-i) + i
             = T(n-(n-1) + (n-1)
             = T(n-n+1) + (n-1)
             = T(1) + (n-1)
             = 0 + (n-1)
             = n-1 ∈ O(n)

3.  Contoh kasus mencari faktor persekutuan besar  

     function FPB (input m, n: integer) → integer

     Algoritma :

if (m=0) then

                 FPB ← n

              else if (m < n) then

                         FPB ← FPB (n, m)

                     else

                         FPB ← FPB (m mod n, n)

                     endif

               endif

     endfunction
 
    Operasi dasar utama : mod
    Rekurens : FPB(m mod n)
    Pengehenti : m < n 
    a.  jika m=0 maka n adalah FPB.
    b. jika m<n maka m adalah FPB (m,n) ; berhenti.
    c. jika tidak maka masuk ke langkah selanjutnya.
    d. m dibagi dengan n dan dimisalkan r adalah sisanya.
    e. ganti nilai m dengan nilai n dan nilai n dengan r, lalu ulangi ke langakah 1.

    Contoh :
      
     Karena sisa terakhir adalah nol maka FPB dari 312 dan 70 adalah sisa sebelumnya yaitu 2.
     

         

 

      [n log r = log rn < log Fn < log N => nlogN/logr ∈ O(logN)]
      Kompleksitas waktu logaritmik ini berarti, laju pertumbuhan waktunya lebih lambat 
      dari pada pertumbuhan n