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

Read more

Algoritma Greedy

Definisi Algoritma Greedy

Algoritma Greedy Merupakan jenis algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara pada setiap langkahnya. Nilai maksimun sementara ini dikenal dengan istilah local maksimum. Pada kebanyakan kasus algoritma greedy tidak akan menghasilkan solusi paling optimal begitupun algoritma greedy biasanya memberikan solusi yang mendekati nilai optimum dalam waktu yang cukup cepat.

Algoritma greedy membenttuk solusi langkah perlangkah ( step by step ). Terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi, karenanya pada setiap langkah harus dibuat keputusan yang teerbaik dalam menentukan pilihan.

   Contoh kasus1

    Masalah penukaran uang

           Nilai uang yang ditukar: A

           Himpunan koin (multiset):  {d₁, d₂, …, d_n}.

           Himpunan solusi: X = {x₁, x₂, …, x_n},

           x_i = 1 jika d_i dipilih, x_i = 0 jika d_i tidak dipilih.     

            Penyelesaian dengan algoritma greedy

          a. Strategi greedy:  Pada setiap langkah, pilih koin dengan nilai  terbesar dari himpunan 
              koin yang tersisa.

          b. Agar pemilihan koin berikutnya optimal, maka perlu mengurutkan himpunan koin dalam 
              urutan yang menurun (noninceasing order).

          c. Jika himpunan koin sudah terurut menurun, maka kompleksitas algoritma greedy = O(n).

          d. Sayangnya, algoritma greedy untuk masalah penukaran uang ini tidak selalu 
              menghasilkan solusi optimal (lihat contoh sebelumnya).

      Pseudocode:

function CoinExchange(input C : himpunan_koin, A : integer) ← himpunan_koin

{ mengembalikan koin-koin yang total nilainya = A, tetapi jumlah koinnya minimum }

Deklarasi :

   S : himpunan_koin

   x : koin

Algoritma:

                S ← {}

                while (å(nilai semua koin di dalam S) ¹ A) and (C ¹ {} ) do

                         x ← koin {yang mempunyai nilai terbesar}

                         C ← C - {x}

                        if  (å(nilai semua koin di dalam S) + nilai koin x £ A then

                                S ← S È {x}

                        endif

                endwhile

                if (å(nilai semua koin di dalam S) = A then

                   return S

                else

                write(’tidak ada solusi’)

                endif

endfunction 



Contoh kasus 2

contoh penerapan greedy didalam transportasi

Pada tabel 1 terdapat sebuah alat angkut dengan kapasitas 100kg terdapat 4 buah barang dengan ukuran sebagai berikut :

 

Maka dengan menggunakan algoritma greedy diperoleh tabel 2 sebagai berikut : 

Keterangan:

GBW : Greey By weight

GBP : Greedy By Profit

Gbd: Greedy By Density

0 : Barang tidak diangkut

1 : Barang diangkut

Berdasarkan teori dan contoh algoritma greedy dalam menyelesaikan Knapsack Problem maka pseudocode algoritma greedy adalah sebagai berikut:

function Knapsack(input C: himpunan_objek, K : real) → himpunan_solusi

{menghasilkan solusi persoalan knapsack dengan algoritma greedy yang menggunakan strategi pemilihan objek berdasarkan profit(pi), weight(wi), density(pi/wi). Soulsinya dinyatakan sebagai vektor X = x[1], x[2], ... , x[n].

Asumsi : untuk greedy by profit seluruh objek sudah terurut berdasarkan nilai pi yang menurun. Untuk greedy gy weighted seluruh objek sudah terurut berdasar nilai wi yang menaik. Untuk greedy by density seluruh objek sudah terurut berdasarkan nilai pi/wi yang menurun}

Deklarasi :

            i,totalbobot : integer

           available : boolean

           x : himpunan_solusi 

Algoritma :

             for i ← 1 to n do

             x[i] ← 0 

             endfor

             i ← 0

             totalbobot ← 0

             available ← true

             while (i < n) and (available) do

                    i ← i + 1

                    if totalbobot + w[i] ← K then

                        x[i] ← 1

                        totalbobot ← totalbobot + w[i]

                    else

                        available ← false

                        x[i] ← 0

                    endif

             endwhile

endfunction

Read more