Menghitung T(n) Pseudocode Rekursif

Program Menghitung Min Max

Procedure MinMaks(input n = TabelInt,I,j:integer, output min, maks: integer)

{I.S. : }

{F.S. : }

Kamus :

min1, min2, maks1, maks2 :integer

Algoritma :

if (i = j) then

  min ← ni

  maks←ni

  else

   if(i=j-1) then

    min←ni

    maks←ni

    else

     maks←ni

     min←ni

   endif

else

k←(i+j) div 2

MinMaks(n, i, k, min1, maks1)

MinMaks(n, i, k+1, j, min2, maks2)

If(min1<min2)then

  min←min1

  else

min←min2

endif

if (maks<maks2)then

maks←maks2

else

maks←maks2

endif

Mencari T(n)

Relasi rekurrens :

                0                         ,n=1

T(n) =      1                          ,n=2

                2T(n/2)+2            ,n>2

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

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

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

T(n)        =…..

T(n)        =2^k-1 T(2)+∑_i=1^k-12ⁱ

T(n)        =2^{k-1 .} . 1+2^k-2

T(n)        = 2(²log n )^-1+2(² log n)-2

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

T(n)        =3n/2 – 2

T(n)        = 3n/2-2

Jadi T(n) € O(n)

Menghitung T(n) Pseudocode Rekursif

Program Tower Hanoi

Procedure Hanoi (Input N,A,B,C : integer)

{I.S. : }

{F.S. : }

Kamus :

Algoritma :

If N = 1

  then

  Output (‘Pindahkan Piringan dari ‘,A,’Ke’,B)

Else Hanoi (n-1,A,C,B)

Output(‘Pindahkan Piringan dari ‘,A,’Ke’,B)

Hanoi(n-1, C,B,A)

Endif

Mencari T(n)

 

Operasi Dasar(=)

Kompleksitas Waktu

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

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

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

       =   .................

       =   .................

       = (1+2+2²+....+2ⁿ⁻²)+2ⁿ⁻¹T(1)

      = 1+2+2²+.....+2ⁿ⁻¹

      = 2ⁿ⁻¹

Jadi

T(n) = 2ⁿ⁻¹

T(n) € О(2ⁿ)

Relasi rekurrens

                1                        ,n=1

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

Mencari T(n) dari Psedocode Rekursif

Psedocode Subrutin Rekursif Faktorial N

Function Faktorial Input  N : integer) ← real

{I.S.  : faktorial dari harga N sudah terdefinisi}

{F.S. : menghasilkan fungsi faktorial N}

Kamus:

    Fak   : real

    i      : integer

Algoritma:

    if   (N = 0) or (N = 1)  then

           Faktorial  N ←  1

     else

           Fak  ←  1

           for  i  ←  2   to   N   do

                Fak  ← Fak  *  i  

           endfor

           Faktorial  ←  Fak

     Endif

EndFunction

Menghitung T(n)

Operasi Dasar	Cop	C(n)
*         = 1 =         = 2    ←         = 4n+1	a b c	1na 2nb (4n+1)c

n = N

T(n) = Cop . C(n)

        = (1na) + (2nb) + (4n+1)c
        = 1na + 2nb + 4nc + 1c