Menghitung Kompleksitas Waktu Algoritma Rekursif

1. Algoritma Menghitung Nilai x Pangkat y

Program Pangkat

Kamus

x,y : integer

Function pangkat (x:integer, y: integer)

Algoritma

if y = 0 then

return 1

else

return x*pangkat(x,y-1)

endif

endfuction

algoritma

     input x,y

     output pangkat(x,y)

Analisis:

- Kompleksitas waktu diukur dari jumalh operasi perkalian (*)

- Jika y = 0 maka pangkat sama dengan 1 (tidak ada operasi perkalian) {basis}

     - Jika y > 0 maka,

pangkat(x,y) = x * pangkat(x,y-1) atau x^y =      x * x^y-1  (ada operasi perkalian) {rekurens}

- Yang mempengaruhi jumlah pemanggilan rekursif adalah nilai y atau (y-1) atau T(n-1)

T(n) = 1 + T(n-1) ; n > 0 {rekurens}

T(n) = 1 ; n = 0          {basis}

    

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

           = 1 + 1 + T(n-2)

           = 2 + 1 + T(n-3)

           …

     T(n) = n + T(0)

     Jadi T(n)= n ≈ O(n)

2. Algoritma Menentukan Deret bilangan Fibonacci ke-n

Function fib (input n : integer) → integer

Deklarasi

-

Algoritma

     If (n = 0) or (n = 1) then

           Return n

     Else

           Return fib(n-1) + fib(n-2)

     endif

Analisis:

- Kompleksitas waktu diukur dari jumalh operasi samadengan (=)

n = 0 atau n = 1 {basis}

fib(n-1) + fib(n-2) {rekurens}

- T(n)= 2 + T(n-1) + T(n-1) ; n > 1 {rekurens}

  T(n)= 1 ; n = 0 = 1      {basis}

  T(n-1)≈T(n-2)

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

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

           = 4T(n-2)+6 ; k=2 , C=2

           = 8T(n-3)+14 ; k=3 , C=2

           …

  T(n)     = 2^kT(n-k)+(2^k-1)C

           (n-k) = 0 → k=n

  T(n)     = 2ⁿT(0)+(2ⁿ-1)C

  T(n)     = (1+C)*2ⁿ-C

  Jadi T(n)≈ 2ⁿ ≈ O(2ⁿ)

3. Algoritma

Procedure MinMaks2(input A : TabelInt, i, j : integer, output min, maks : integer) 

{ Mencari nilai maksimum dan minimum di dalam tabel A yang berukuran n elemen secara Divide and Conquer. Masukan: tabel A yang sudah terdefinisi elemenelemennya Keluaran: nilai maksimum dan nilai minimum tabel }

Deklarasi

min1, min2, maks1, maks2 : integer

Algoritma

     if i=j then { 1 elemen }

min ← Ai

maks ← Ai

else

if (i = j-1) then { 2 elemen }

if Ai < Aj then

maks ← Aj

min ← Ai

else

maks ← Ai

min ← Aj

endif

else { lebih dari 2 elemen }

k ← (i+j) div 2  { bagidua tabel pada posisi k } MinMaks2(A, i, k, min1, maks1)

MinMaks2(A, k+1, j, min2, maks2)

if min1 < min2 then

min ← min1

else

min ← min2

endif

if maks1<maks2 then

maks ← maks2

else

maks ← maks2

endif

Analisis:

T(n) = 0; n=1 {basis}

T(n) = 1; n=2 {basis}

T(n) = 2T(n/2)+2 ; n>2 {rekurens}

Asumsi n = 2^k, dengan k bilangn bulat positif, maka:

T(n) = 2T(n/2)+2

     = 2(2T(n/4) + 2) + 2 = 4T(n/4) + 4 + 2

     = 4 (2T(n/8) + 2) + 4 + 2 = 8T(n/8) + 8 + 4 + 2

     = ...           ­_k-1

     = 2k – 1 T(2) +      ∑ 2ⁱ

                     ⁱ⁼¹

     = 2k – 1  1 + 2k – 2

     = 2^(2logn)-1 + 2^(2logn)-2

     = n/2 + n-2

     =3n/2-2

Jadi T(n) = n = O(n)

resource : 

https://bertzzie.com/knowledge/analisis-algoritma/KompleksitasAlgoritma.html

https://www.youtube.com/watch?v=gCsfk2ei2R8

http://documents.tips/documents/analisis-algoritma-non-rekursif-dan-rekursifppt.html#

buku Algoritma dan Pemrograman, Renaldi Munir

Menghitung Efisiensi Waktu Dengan rumus Sigma

1. Algoritma Penjumlahan Deret

Program penjumlahanderet

Deklarasi

n, i, jumlah : integer

Algoritma

Read(n)

jumlah ← 0

For i ←  1 to n do

jumlah ← jumlah + 1

Endfor

Write(jumlah)

Analisis:

_n

∑  = n-1+1

ⁱ⁼¹

    ≈ n ϵ Θ(n)

2. Alagoritma Menampilkan Bintang

Program menampilkanbintang

Deklarasi

i, j, n : integer

Algoritma

Read(n)

For i <- 1 to n do

          For j <- 1 to n do

               Write(‘*’)

          Endfor

     Endfor

Analisis:

_{n     n      n}

∑    ∑ 1 = ∑  n-1+1

^{i=1   j=1    i=1}

             _n

      = ∑  n

         ⁱ⁼¹

      = (n-1)n

           = n²-n ≈ n²  ϵ Θ(n²)

3. Algoritma Mencari Maks

Program mencari_maks (input A : LarikInt, input n : integer, output maks : integer)

Deklarasi

i : integer

Algoritma

maks ß A[1]

for i ß 2 to n do

            if A[i] > maks then

              maks ß A[i]
            endif

endfor

Analisis :

_n

∑  = n-2 +1

ⁱ⁼²

_­   = n-1 _­­^­­ ≈ n ϵ Θ(n)

4. Algoritma Menentukan Faktorial

Program faktorial (input a₁..a_n : integer)

Deklarasi :

i : integer

fak : real

Algoritma :

Input(n)

If (n = 0) or (n = 1) then

faktorial ß 1

Else

                fak ß 1

                for i ß 2 to n do

                           fak ß fak * i

                endfor

     endif

     output(fak)

Analisis:

­_n

∑ = n-2+1

­­­­­­­_­­­­­ⁱ⁼²

   = n – 1 ≈ n ϵ Θ(n)

5. Algoritma Menghitung Rata - rata

Program HitungRataRata

{Menghitung rata - rata N buah bilangan bulat yang dibaca dari papan ketik. N > 0}

Deklarasi

     N, x, i, jumlah : integer

     r : real                  {rata rata nilai}

Algoritma

     Read(N)

Jumlah ß 0

For i ß 1 to N do

     Read(x)

jumlah ß jumlah + x

     endfor

     r ß jumlah/N

     write(r)

Analisis :

_n

∑  = n-1+1

ⁱ⁼¹

   = n ≈ n ϵ Θ(n)