Analisis Algoritma Rekursif

Rekursif adalah fungsi yang memanggil dirinya sendiri.
Contoh Analisis Matematis Algoritma Rekursif :

Menghitung Faktorial

Function  F(input awal,n : integer) à real

KAMUS:

fak : real

ALGORITMA:

If n = 0 then

            fak <-- 1

else

            fak <-- n * F(n-1)

endif

return fak

endFunction

T(n) ---- 0 , n = 0

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

 

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

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

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

 = …

 = n + T(0)

 = n + 0

Jadi T(n) = n ϵ Ο(n)

======================================

 

Mencari Nilai S

Algortihm S(n)

{input : A positive integer n}

{Output : the sum of the first n cubes}

if n=1 then

return 1

else

return S(n-1) + n * n* n

endif

T(n) ---- 0 , n = 0

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

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

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

 = …

 = n + T(0)

 = n + 0

Jadi T(n) = n ϵ Ο(n)

======================================

Menghitung Deret Aritmatika

Function F(input n : integer) à real

KAMUS

deret : real;

ALGORITMA

if  awal = 0  and n = awal+1 then

deret <-- 1;

else

deret <-- n + F(n-1);

endif

return deret

endFunction

Paling Dalam : +

+ : n

F(n) = n + F(n-1) untuk n > 1

F(n) = 1 untuk n = 1 dan n=0

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)

T(n) = …..

T(n) = n + 0 

T(n) = n

T(n) = n ϵ O(n)

Notasi Asimtotik 1

1. Ο-Notation --> t(n)  ϵ Ο(g(n)) jika t(n)  ≤ cg(n) karena mendekati hasil melalui grafik(g(n)) dari atas.

2. Ω-Notation --> t(n)  ϵ Ω(g(n)) jika t(n)  ≥ cg(n) karena mendekati hasil melalui grafik(g(n)) dari bawah.

3. Θ-Notation --> t(n)  ϵ Θ(g(n)) jika c2g(n) ≤ t(n) ≤ c1g(n) karena mendekati hasil melalui grafik(g(n)) dari atas dan bawah (lebih akurat).

Contoh diambil dari t(n) Postingan sebelumnya\

Cari Minimum

Tmax(n)  : N

Tmin(n)   : 1

Tavg(n)   :  N

Tmax(n) / Worst Case

a.       Ο-Notation n ϵ Ο(g(n²))

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C:1 n0: 0

b.      Θ-Notation n ϵ Θ(g(n²))

C_2g(n) ≤ Tavg(n) ≤ C₁g(n)

Batas Atas :

t(n) ≤ C(g(n))

t(n) ≤ C(n)

n  ≤ n (untuk semua n ≥ 0)

n  ≤ n­²

C₁:1 n₀: 0

Batas Bawah

t(n) ≥ C(g(n))

t(n) ≥ C(n)

n  ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 0

a.       Ω-Notation n ϵ Ω(g(n))

t(n) ≥ cg(n)

n     ≥ n

C:1 n₀: 0

Tmin(n) / Best Case

a.       Ο-Notation 1 ϵ Ο(g(n²))

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

c:1 n0: 1

b.      Θ-Notation 1 ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C₁:1 n0: 1

Batas Bawah

t(n) ≥ cg(n)

1     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 1

c.       Ω-Notation 1ϵ Ω(g(n))

t(n) ≥ cg(n)

1     ≥ n

c:1 n₀: 0

Tavg(n) / Average Case

a.       Ο -Notation n ϵ Ω(g(n))

t(n) ≤ C(g(n))

t(n) ≤ C(n²)

n  ≤ n²

C= 1 ; n₀= 0

b.      Θ-Notation n ϵ Θ(g(n²))

C_2g(n) ≤ Tavg(n) ≤ C₁g(n)

Batas Atas :

t(n) ≤ C(g(n))

t(n) ≤ C(n)          

n  ≤ n (untuk semua n ≥ 0)

n  ≤ n­²

C₁:1 n0: 0

Batas Bawah

t(n) ≥ C(g(n))

t(n) ≥ C(n)

n  ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 0

c.       Ω -Notation n  ϵ Ο(g(n²))

t(n) ≤ C(g(n))

t(n) ≤ C(n)

n  ≤ n (untuk semua n ≥ 0)

n  ≤ n²

C1:1 n0: 0

Function Palindrom

Tmax(n)  : 3 + N

Tmin(n)   : 6

Tavg(n)   : N  

Tmax(n) / Worst Case

a.       Ο-Notation 3+n ϵ Ο(g(n²))

t(n) ≤ cg(n)

3+n ≤ n + n

3+n ≤ 2n  (untuk semua n ≥ 3)

2n ≤ 2n²

C:2 n0: 3

b.      Θ-Notation 3+n ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

3+n ≤ n + n

3+n ≤ 2n  (untuk semua n ≥ 3)

2n ≤ 2n²

C₁:2 n₀: 3

Batas Bawah

t(n) ≥ cg(n)

3+n ≥ n

C₂:1 n₀: 0

C₁: 2 C₂:1 n₀: 3

c.       Ω-Notation 3+n ϵ Ω(g(n))

t(n) ≥ cg(n)

3+n ≥ n

C:1 n₀: 0

Tmin(n) / Best Case

a.       Ο-Notation 6 ϵ Ο(g(n²))

t(n) ≤ cg(n)

6     ≤ n

6     ≤ n  (untuk semua n ≥ 6)

n     ≤ n²

C:1 n0: 6

              

b.      Θ-Notation 6 ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

6     ≤ n

6     ≤ n  (untuk semua n ≥ 6)

n     ≤ n²

C₁:1 n0: 6

Batas Bawah

t(n) ≥ cg(n)

6     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 6

c.       Ω-Notation 6 ϵ Ω(g(n))

t(n) ≥ cg(n)

6     ≥ n

C:1 n₀: 0

Tavg(n) / Average Case

b.      Ο-Notation n  ϵ Ο(g(n²))

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C:1 n0: 0

c.       Θ-Notation n ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C₁:1 n0: 0

Batas Bawah

t(n) ≥ cg(n)

n     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 0

d.      Ω-Notation n ϵ Ω(g(n))

t(n) ≥ cg(n)

n     ≥ n

C:1 n₀: 0

Sisip Belakang

Tmax(n)  : N

Tmin(n)   : 1

Tavg(n)   :  N

Tmax(n) / Worst Case

a.       Ο-Notation n  ϵ Ο(g(n²))

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C:1 n0: 0

b.      Θ-Notation n ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C₁:1 n0: 0

Batas Bawah

t(n) ≥ cg(n)

n     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 0

c.       Ω-Notation n ϵ Ω(g(n))

t(n) ≥ cg(n)

n     ≥ n

C:1 n₀: 0

Tmin(n) / Best Case

a.       Ο-Notation 1 ϵ Ο(g(n²))

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C:1 n0: 1

b.      Θ-Notation 1 ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C₁:1 n0: 1

Batas Bawah

t(n) ≥ cg(n)

1     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 1

c.       Ω-Notation 1ϵ Ω(g(n))

t(n) ≥ cg(n)

1     ≥ n

C:1 n₀: 0

Tavg(n) / Average Case

a.       Ο-Notation n  ϵ Ο(g(n²))

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C:1 n0: 0

b.      Θ-Notation n ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C₁:1 n0: 0

Batas Bawah

t(n) ≥ cg(n)

n     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 0

c.       Ω-Notation n ϵ Ω(g(n))

t(n) ≥ cg(n)

n     ≥ n

C:1 n₀: 0

Hapus Belakang

Tmax(n)  : N

Tmin(n)   : 1

Tavg(n)   :  N

Tmax(n) / Worst Case

a.       Ο-Notation n  ϵ Ο(g(n²))

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C:1 n0: 0

b.      Θ-Notation n ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C₁:1 n0: 0

Batas Bawah

t(n) ≥ cg(n)

n     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 0

c.       Ω-Notation n ϵ Ω(g(n))

t(n) ≥ cg(n)

n     ≥ n

C:1 n₀: 0

Tmin(n) / Best Case

a.       Ο-Notation 1 ϵ Ο(g(n²))

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C:1 n0: 1

b.      Θ-Notation 1 ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C₁:1 n0: 1

Batas Bawah

t(n) ≥ cg(n)

1     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 1

c.       Ω-Notation 1ϵ Ω(g(n))

t(n) ≥ cg(n)

1     ≥ n

C:1 n₀: 0

Tavg(n) / Average Case

a.       Ο-Notation n  ϵ Ο(g(n²))

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C:1 n0: 0

b.      Θ-Notation n ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C₁:1 n0: 0

Batas Bawah

t(n) ≥ cg(n)

n     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 0

c.       Ω-Notation n ϵ Ω(g(n))

t(n) ≥ cg(n)

n     ≥ n

C:1 n₀: 0

Tampil Linked List

Tmax(n)  : 1

Tmin(n)   : 1

Tavg(n)   :  1

Tmax(n) / Worst Case

a.       Ο-Notation 1 ϵ Ο(g(n²))

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C:1 n0: 1

b.      Θ-Notation 1 ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C₁:1 n0: 1

Batas Bawah

t(n) ≥ cg(n)

1     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 1

c.       Ω-Notation 1ϵ Ω(g(n))

t(n) ≥ cg(n)

1     ≥ n

C:1 n₀: 0

Tmin(n) / Best Case

a.       Ο-Notation 1 ϵ Ο(g(n²))

t(n) ≤ cg(n)

1   ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C:1 n0: 1

b.      Θ-Notation 1 ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C₁:1 n0: 1

Batas Bawah

t(n) ≥ cg(n)

1     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 1

c.       Ω-Notation 1ϵ Ω(g(n))

t(n) ≥ cg(n)

1     ≥ n

C:1 n₀: 0

Tavg(n) / Average Case

a.       Ο-Notation 1 ϵ Ο(g(n²))

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C:1 n0: 1

b.      Θ-Notation 1 ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C₁:1 n0: 1

Batas Bawah

t(n) ≥ cg(n)

1     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 1

c.       Ω-Notation 1ϵ Ω(g(n))

t(n) ≥ cg(n)

1     ≥ n

C:1 n₀: 0