Algoritma Rekursif

Mencari T(n) Untuk Algoritma Rekursif

MEMBALIKKAN URUTAN ANGKA BILANGAN BULAT (REKURSIF)

Seperti : 123 menjadi 321

ALGORITMA :

Procedure BalikAngka (input n: integer) { membalikkan urutan bilangan bulat n   K.Awal   : nilai n sudah terdefinisi   K.Akhir  : urutan angka bilangan n dicetak terbalik      basis      : jika n < 10, cetak (n)      rekurens   : jika n > 10 maka                      - cetak (n mod 10)                      - BalikAngka (n div 10) } Deklarasi  - Algoritma  if (n < 10) then      write(n)             { basis }  else                     { rekurens }      write(n mod 10);      BalikAngka(n div 10);  endif

MENGHITUNG T(n):

T_min(n) = 1

T_max(n) = 1

T_avg(n) = ( 1 + 1 ) / 2

= 2 / 2

= 1

Algoritma Pangkat Secara Rekursif

Kamus :

                m, n : integer

Algoritma :

                Function pangkat(m : integer, n : integer) : integer

                If (n = 0) then

                                Pangkat <-- 1

                Else

                                Pangkat <-- m * pangkat(m, n - 1)

                Endif

                Endfunction

               

                Input(m, n)

                Output pangkat(m, n)

Menghitung menggunakan <-- (Assignment)

T_min(n) = 1

T_max(n) = 1

T_avg(n)   = (1+1)/2

= 2 /2

= 1

function Faktorial(n:integer) : integer;
begin
 if n=0 then
   Faktorial ç1
else
    Faktorial ç n * Faktorial(n-1);
 end;
- See more at: http://emerer.com/algoritma-rekursif-dengan-pascal/#sthash.rCjJqUS4.dpuf

function Faktorial(n:integer) : integer;
begin
 if n=0 then
   Faktorial ç1
else
    Faktorial ç n * Faktorial(n-1);
 end;
- See more at: http://emerer.com/algoritma-rekursif-dengan-pascal/#sthash.rCjJqUS4.dpuf

Function Faktorial(n:integer) : integer;
begin

if n=0 then

Faktorial :=1

else

Faktorial := n * Faktorial(n-1);

end;

Menghitung T(n)

T_min(n)   = 1

T_max(n)   = 1

T_avg(n)    = (1+1)/2

   = 2 /2

               = 1


Sumber Referensi :
Munir, Rinaldi, Algoritma & Pemprograman Dalam Bahasa Pascal dan C Edisi Revisi, Informatika, 2011.

Kompleksitas Algoritma, Ken Kinanti Purnamasari

Notasi Asimtotik

NOTASI ASIMTOTIK

Algoritma Nilai Mahasiswa

T_min(n) = 2n

T_max(n) = 2n

T_avg(n) = 2n

Karena T_min, T_max  & T_avg  memiliki nilai yang sama maka akan dituliskan 1x

Big oh

2n < cg(n)

2n < 2n                 (untuk semua n > 0)

C = 2, n₀ = 0

Big omega

2n >  cg(n)

2n > n²                             (untuk semua n < 0)

2n > 2n²

C = 2, n₀ = 0

Big Theta

c₂g(n) < 2n < c₁g(n)

        Batar atas

          2n(n-1) = 2n² – 2n < 2n²                  (untuk  semua n > 0)

          Batas bawah

          2n(n-1) = 2n² – 2n

          2n² – 2n > 2n² – 2n 1/2n                  (untuk  semua n > 2)

c₂ = 2, c₁ = 2, n₀ = 2

MENGHITUNG PERPANGAKATAN

MENGHITUNG NILAI MINIMUM