Analisis Matematis Algoritma Rekursif Fungsi Fibonacci

function fibonacci(Input n:integer)→integer

Kamus

Algoritma

  If (n=0)

    Then

       fibonacci ← 1

    Else

       If (n=1)

         Then

                fibonacci ← 1

         Else

                Fibonacci ← (fibonacci(n-1) + fibonacci(n-2))

      Endif

   Endif

Endfunction

Operasi Dasar Utama : Penjumlahan

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

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

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

T(n) = 1 + 3(1 + T(n-4) + T(n-5))

T(n) = ...

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

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

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

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

Jadi, T(n) =  n + (n-(n-2))

Analisis Matematis Algoritma Rekursif Fungsi Menghitung Deret Aritmatika

Function S(input n:integer)→integer

Kamus

Algoritma

    If (n=1)

         Then

               Hasil ←1

         Else

              Hasil←n + S(n-1)

  Endif

Endfuction

Operasi Dasar Utama : Penjumlahan

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

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 + T(n-n)

T(n) = n + T(0)

T(n) = n + 0

T(n) = n                               

Jadi, T(n) = n

Analisis Matematis Algoritma Rekursif Fungsi Faktorial

function faktorial(Input n:integer)→ integer

Kamus

Algoritma

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

    Then

       Fak← 1

   Else

       If  (n>1)        

          then

               Fak← Faktorial(n-1)*n

          Else

               Fak←0

      Endif

  Endif

Endfunction

Operasi Dasar Utama : Perkalian

T(n) = T(n-1) * n                               dimana n > 1

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 + T(n-n)

T(n) = n + T(0)

T(n) = n + 0

T(n) = n                               

Jadi, T(n) = n

Notasi Asimtotik dari worst case, best case dan average case program segitiga pascal

Program Segitiga_pascal

kamus 

i,j,n : Integer

    p   : array [1..50,1..50] of integer

Algoritma

  read(n);

  for i ß 1 to n do

       for j ß 1 to i do

           if (j =1) or (j = i)
                then
                                p[i,j] ß 1

                else

                                p[i,j] ß p[i-1,j] + p[i-1,j-1]

           write(p[i,j],'    ')

       Endif

  Endfor  Endfor

Terdalam (+)

Tmin  = 0

Notasi O

t(n)  CO(g(n))
t(n) ≤ O(g(n))
0 ≤ n
n = 0               0 _≤ 0
n = 1               0 ≤ 1
n = 6               0 ≤  6
n = 100                            0  ≤  100  

n₀ = 0
C = 1

Notasi Asimtotik Dari Worst case, Best case,dan Average case Program Faktorial

program Faktorial

kamus

   n,fak,i : integer

Algoritma

       read(n)

       fak ß 1

       for i ß n downto 1 do

                fak ß fak * i 

                write(i)

                if   i = 1

                   then

                            write('')

                   else

                            write('*')

                endif

           endfor

terdalam (write)

TMin   = 2n ≈ n

Notasi O

t(n)  CO(g(n))
t(n) ≤ O(g(n))
2n ≤ 3n
n = 0               0 _≤ 0
n = 1               2 ≤ 3
n = 3               6 ≤ 9
n = 100    200  ≤  300                    

n₀ = 0
C = 3 

Notasi Asimtotik dari Worst case, Best case, Average case Algoritma Menghitung Persegi

Menghitung_persegi

Deklarasi

I,j,n : integer

Algoritma

Input(n)

For i← 1 to n do

   For j← 1 to n do

         If (i>j)

                        then

                                    output(“*”)

                        else

                                    output(“ “)

               endif

     endfor

endfor

Worst case, Best case, Average case

T_min(n) = n²

O (Big Oh)

      n²    O (n²)

      n²  ≤  2n²                  (untuk semua n ≥ 0)

      c = 2, n₀ = 0

Ω (Big Omega)

      n²    Ω (n²)

      n²   ≥  ½ n²               (untuk semua n ≥ 1)

      c = ½ , n₀ = 1

Notasi Asimtotik dari worst case, best case, average case algoritma mencari bilngan prima

bil_prima

Deklarasi

 i,bil,b :interger

Algoritma

b←0

input(bil)

for i ←1 to bil do

                if (bil mod i = 0)

                                then

                                                b←b+1

                endif

endfor

                if b = 2 

                                then

                                                output(bil,”bilangan prima”)

                                else

                                                output(bil,”bukan bilangan prima”)

                endif

                

Worst case, Best case, Average case

T_min(n) = 2

O (Big Oh)     

      2   O (n⁰)

      2  ≤  3n⁰                   (untuk semua n ≥ 1)   

      c = 3 , n₀ = 1

Notasi Asimtotik dari Worst case, Best case dan Average case algoritma mencari nilai minimum

procedure NilaiTerrendah (Input N:integer a₁,. . .,a_n:integer)

Deklarasi

   i:integer;

   terrendah:real;

Algoritma:

    terrendah ← a₁

    for i ←2 to N do

      if (a_i< terrendah)

        terrendah ← a₁

      endif

    endfor

    Output('Nilai Akhir Terrendah : ',terrendah:0:2);

Endprocedure

Worst case, Best case, Average case

Yang di hitung adalah < (perbandingan)                                

T_min(n)  = n -1

O (Big Oh)     

      n – 1     O (n)

      n – 1   ≤  2n             (untuk semua n ≥ 1)   

      c = 2, n₀ = 1

Ω (Big Omega)

      n – 1     Ω (n)

      n – 1   ≥ ½ n             (untuk semua n ≥ 2)

      c = ½ , n₀ = 2