30/11/16

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)

29/11/16

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)

02/11/16

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

  c= 3      c= 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

  c= 3      c= 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

  c= 3      c= 2     n = 2

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

  c= 4                        c= 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

  c= 2      c= 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

  c= 3     c= 2     n = 2





Terimakasih Telah Membaca Blog Kami ^_^
(F)