Analisis Algoritma Rekursif

Algoritma Rekursif

function FIBO(input N : integer) → integer

{mengirimkan bilangan fibbonacci dengan cara rekursif}

Algoritma:

int fibo(int n)

   if(n==0)

     return 0;

   else if(n==1)

     return 1;

   else

     //fungsi rekursif

     return fibo(n-1)+fibo(n-2);

Kompleksitas Waktu :

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

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

         =.....

         =.....

         =.....

T(n) =   3×T(n-1) 

T(n) = O(3n )

Read More

Algoritma Greedy

Pengertian Algoritma Greedy

Algoritma Greedy merupakan metode yang populer untuk memecahkan persoalan optimasi. Algortima greedy membentuk solusi langkah per langkah (step by step) dan pada setiap langkah terdapat banyak pilihan untuk dieksplorasi. Oleh karena itu dalam setiap langkah diperlukan keputusan terbaik dalam menentukan pilihan. Algoritma greedy memiliki prinsip yaitu, "take what you get now" dengan kata lain greedy itu rakus atau tamak. Greedy memiliki 2 optimasi yaitu, Maximization (maksimal) dan Minimization (minimum). 
Elemen - Elemen Greedy :
1. Himpunan Kandidat
2. Himpunan Solusi
3. Fungsi Seleksi
4. Fungsi Kelayakan
5. Fungsi Obyektif

Contoh Kasus Algoritma Greedy

Kasus penukaran uang:

Diberikan uang senilai 8500. Tukar 8500 dengan koin - kooin uang yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut?

Jawab: Tersedia banyak koin 500, 1000, 2000, 5000

Uang senilai 8500 dapat ditukar dengan banyak cara berikut:

   8500 = 500 + 500 + 500 +...+ 500                                                                   (17 Koin)

   8500 = 1000 + 1000 + 1000  + 1000 + 1000 + 1000 + 1000 + 1000 + 500    ( 9 Koin)

   8500 = 2000 + 2000 + 2000 + 1000 + 500 + 500 + 500                                  ( 7 Koin)

       |

       |    

     dst.

   8500 = 5000 + 2000 + 1000 + 500                                                                  ( 4 Koin) --> Minimum

Contoh Algoritma Greedy

Algoritma TukarUang(input C : himpunan_koin, A : integer)à himpunan_koin

{ Menghasilkan koin-koin dengan total nilai = A dengan jumlah minimum}

Deklarasi

  x : koin   

  S : himpunan_koin

Algoritma

S ß {}

while (jumlah nilai semua koin dalam S <> A ) AND (C <> {}) do

  x ß koin dengan nilai terbesar

  C ß C – {x}

  if (jumlah nilai semua koin dalam S) + nilai koin x < A then

  S ß S U {x}

  endif

endwhile

if (jumlah nilai semua koin dalam S) = A then

  return S

else

  write(‘tidak ada solusi’);

endfor

Read More

Analisis Algoritma Rekursif

Algoritma Rekursif

function Faktorial (input n : integer) → integer
{menghasilkan nilai n!, n tidak negatif}s waktu

Algoritma :

 if n=0 then

   return 1

else

    return ( n*faktorial (n-1))

 endif;


Kompreksitas waktu :

T(n) = 1+T(n-1)
T(n) = 1+1+T(n-2)=2+T(n-2)
T(n) = 2+1+T(n-3)=3+T(n-3)
     = ...
     = ...
     = n+T(0)
     = n+0
T(n) =n
T(n) =T(n)ϵO(n)

Read More

Analisis Algoritma Rekursif - Pangkat

Algoritma Rekursif Pangkat

function Pangkat(x, y : integer) → integer
Deklarasi lokal :
{tidak ada}
Algoritma :
        if y=0 then
           return 1
        else
          return (x*Pangkat(x,y-1))
        endif.

operasi dasar utama : perkalian (*) (1 kali)

T(n) = 0                  , n = 0
T(n) = T(n - 1) + 1 , n > 0

T(n) = T (n - 1) + 1
        = T (n - 1 - 1) + 1 = T(n - 2) + 1
        = T (n - 2 -1) + 1 = T(n - 3) + 1
            |
            |
            |
T(n) = (n - i) + i
T(n) = (n - n) + n
T(n) = n
T(n) = n ϵ  O (n)

Read More

Notasi Asimptotik (Big Oh (O), Big Omega (Ω) , Big Theta (Θ) )

Menghitung Big Oh (O), Big Omega (Ω) , Big Theta (Θ)

~) Tmin = 2
- Big Oh (O)
  T(n) ε O (g(n))
  T(n) ≤ C (g(n))
    2    ≤  ... n          ( untuk semua n >  2 )
    2n + 2   ≤  3n
 C = 3  nₒ = 2

- Big Omega (Ω)

  T(n) ε Ω (g(n))

  T(n) ≥ C g(n)
    2    ≥  ... n          ( untuk semua n ≥  1 )
    2    ≥  2 n
 C = 2  nₒ = 1

- Big Theta (Θ)

  T(n) ε Θ (g(n))

  c2g(n) ≤ t(n) ≤ c1g(n)

  Batas Atas 
    2    ≤  ... n          ( untuk semua n  ≥ 2 )
   2n + 2   ≤  3n

  Batas Bawah
   2    ≥  ... n          ( untuk semua n ≥  1 )
   2    ≥  2 n

  c1 = 3      c2 = 2     nₒ = 2

~) Tmax = n + 2 

- Big Oh (O)
  T(n) ε O (g(n))
  T(n) ≤ C (g(n))
    n + 2    ≤  ... n          ( untuk semua n ≥  3 )
    n + 2    ≤  3 n
 C = 3  nₒ = 3

- Big Omega (Ω)
  T(n) ε Ω (g(n))
  T(n) ≥ C g(n)
    n + 2    ≥  ... n          ( untuk semua n ≥  2 )
    n + 2    ≥  1 n
 C = 1  nₒ = 2


- Big Theta (Θ)
  T(n) ε Θ (g(n))
  c2g(n) ≤ t(n) ≤ c1g(n)

  Batas Atas 
    n + 2    ≤  ... n          ( untuk semua n ≥  3 )
    n + 2    ≤  3 n

  Batas Bawah
   n + 2    ≥  ... n          ( untuk semua n ≥  2 )
   n + 2    ≥  1 n

  c1 = 3      c2 = 1     nₒ = 3

~) Tavg = 2n  

  - Big Oh (O)
  T(n) ε O (g(n))
  T(n) ≤ C (g(n))
    2n    ≤  ... n          ( untuk semua n ≥  2 )
    2n    ≤     3 n 
 C = 3  nₒ = 2

- Big Omega (Ω)
  T(n) ε Ω (g(n))
  T(n) ≥ C g(n)
   2n     ≥  ... n          ( untuk semua n ≥  2 )
   2n     ≥  2 n
 C = 2  nₒ = 2


- Big Theta (Θ)
  T(n) ε Θ (g(n))
  c2g(n) ≤ t(n) ≤ c1g(n)

  Batas Atas 
    2n     ≤  ... n          ( untuk semua n ≥  2 )
    2n     ≤  3 n

  Batas Bawah
   2n     ≥  ... n          ( untuk semua n ≥  2 )
   2n     ≥  2 n

  c1 = 3      c2 = 2     nₒ = 2

Read More

Notasi Asimptotik (Big Oh (O), Big Omega (Ω) , Big Theta (Θ) )

Menghitung Big Oh (O), Big Omega (Ω) , Big Theta (Θ)

~) Tmin = 2
- Big Oh (O)
  T(n) ε O (g(n))
  T(n) ≤ C (g(n))
    2           ≤  ... n 
    2n + 2  ≤  2n + 2n        ( untuk semua n ≥  1 )
    2n + 2  ≤  4n  
 C = 4  nₒ = 1

- Big Omega (Ω)

  T(n) ε Ω (g(n))

  T(n) ≥ C g(n)
    2n + 2   ≥  ... n          ( untuk semua n ≥  1 )
    2n + 2   ≥   2n
 C = 2  nₒ = 1

- Big Theta (Θ)

  T(n) ε Θ (g(n))

  c2g(n) ≤ t(n) ≤ c1g(n)

  Batas Atas 
    2    ≤  ... n          ( untuk semua n ≥  1 )
    2n + 2    ≤  4n

  Batas Bawah
   2    ≥  ... n          ( untuk semua n ≥  1 )
   2n + 2    ≥  2 n

  c1 = 4                        c2 = 2               nₒ = 1

~) Tmax = n + 2 

- Big Oh (O)
  T(n) ε O (g(n))
  T(n) ≤ C (g(n))
    n + 2    ≤  ... n        ( untuk semua n ≥  2 )
    n + 2    ≤  2 n
 C = 2  nₒ = 2


- Big Omega (Ω)
  T(n) ε Ω (g(n))
  T(n) ≥ C g(n)
    n + 2    ≥  ... n          ( untuk semua n ≥  2 )
    n + 2    ≥  1 n
 C = 1  nₒ = 2


- Big Theta (Θ)
  T(n) ε Θ (g(n))
  c2g(n) ≤ t(n) ≤ c1g(n)

  Batas Atas 
    n + 2    ≤  ... n          ( untuk semua n ≥  2 )
    n + 2    ≤  2 n

  Batas Bawah
   n + 2    ≥  ... n          ( untuk semua n ≥  2 )
   n + 2    ≥  1 n

  c1 = 2      c2 = 1     nₒ = 2

~) Tavg = 2n + 2 

  - Big Oh (O)
  T(n) ε O (g(n))
  T(n) ≤ C (g(n))
    2n + 2    ≤  ... n
    2n + 2    <  2n + n          ( untuk semua n ≥  2 )
    2n + 2    ≤  3 n
 C = 3  nₒ = 2


- Big Omega (Ω)
  T(n) ε Ω (g(n))
  T(n) ≥ C g(n)
   2n + 2    ≥  ... n          ( untuk semua n ≥  2 )
   2n + 2    ≥  2 n
 C = 2   nₒ = 2


- Big Theta (Θ)
  T(n) ε Θ (g(n))
  c2g(n) ≤ t(n) ≤ c1g(n)

  Batas Atas 
    2n + 2    ≤  ... n          ( untuk semua n ≥  2 )
    2n + 2    ≤  3 n

  Batas Bawah
   2n + 2    ≥  ... n          ( untuk semua n ≥  2 )
   2n + 2    ≥  2 n

  c1 = 3     c2 = 2     nₒ = 2




Terimakasih Telah Membaca Blog Kami ^_^
(F)

Read More