Menghitung worst case, best case dan average case dari 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

Tmax = n - 2

Tavg  = (n – 2) / 2

          ≈  n – 2

Menghitung 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

TMax  = 2n ≈ n

Tavg    = (2n + 2n)/2
            = 2n

            ≈ n

Menghitung 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²

T_max(n) = n²

T_avg(n) = n² ≈ n

Menghgitung 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

T_max(n) = n -1

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

              ≈ n -1 / 2

              ≈ n

Menghitung worst case, best case, average case dari 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

T_max(n) = n +1

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

      ≈  n+1 /2

                    ≈ n

Efisiensi Waktu Dalam Algoritma

Menghitung_lama_proyek

{I.S. : masukkan waktu dalam hari}

{F.S. : menampilkan keterangan tahun, bulan, dan hari}

Kamus :

                Waktu, tahun, sisa, bulan, hari : integer

Algoritma :

                Input(waktu)                            //input dalam hari

                Tahun ß waktu div 365

                Sisa ß waktu Mod 365  

                Bulan ß sisa div 30

                Hari ß sisa Mod 30

                Output(tahun, bulan, hari)

Operasi pengisian

Sintaks	Jumlah
Input(waktu)	1
Tahun ß waktu div 365	1
Sisa ß waktu Mod 365	1
Bulan ß sisa div 30	1
Hari ß sisa Mod 30	1
Total	5

Operasi pembagian

Sintaks	Jumlah
waktu div 365	1
waktu Mod 365	1
sisa div 30	1
sisa Mod 30	1
Total	4

Operasi pengeluaran

Sintaks	Jumlah
Output(tahun)	1
Output(bulan)	1
Output(hari)	1
Total	3

Total T(n)=CopC(n)

C(n)	Cop	T(n)
5	A	5a
4	B	4b
3	C	3c

Total kebutuhan waktu eksekusi algoritma HitungRata2 :

Total Waktu = t1 + t2 + t3 =  5a+4b+4c

PenjumlahanDeret

Kamus :

n,I,jumlah : integer

algoritma :

input(n)

                jumlah ß 0

                i ß 1

while (i <= n) do

jumlah ß jumlah + i

i ß i + 1

endwhile                output(jumlah)

Oprasi pengisian

Sintaks	Jumlah
input(n)	1
jumlah ß 0	1
jumlah ß jumlah + i	n
i ß i + 1	n
total	2n +2

Operasi perbandingan

Sintaks	Jumlah
i <= n	n + 1
total	n + 1

Operasi penjumlahan

Sintaks	Jumlah
jumlah + i	n
i ß i + 1	n
total	2n

Opersi pengeluaran

Sintaks	Jumlah
output(jumlah)	1
total	1

Total T(n)=CopC(n)

C(n)	Cop	T(n)
2n + 2	A	(2n+2)a
n + 1	B	(n+1)b
2n	C	2nc
1	D	D

Total kebutuhan waktu eksekusi algoritma HitungRata2 :

Total Waktu = t1 + t2 + t3 + t4 =  (2n+2)a + (n+1)b + 2nc+d

Massa_Jenis_Benda

Kamus :

m,v,r : integer

algoritma :

input(m)

input(v)

                r ßm/v

output(r)

Oprasi pengisian

Sintaks	Jumlah
input(m)	1
Input(v)	1
r ß m/v	1
total	3

Operasi penjumlahan

Sintaks	Jumlah
r ß m/v	1
total	1

Opersi pengeluaran

Sintaks	Jumlah
output(r)	1
total	1

Total T(n)=CopC(n)

C(n)	Cop	T(n)
3	A	3a
1	B	b
1	C	c

Total kebutuhan waktu eksekusi algoritma HitungRata2 :

Total Waktu = t1 + t2 + t3  =  3a + b + c

Menghitung_hasil_Pangkat

{I.S :}

{F.S:}

Deklarasi

Angka, pangkat, hasil: integer

Algoritma

                Input(angka)                                      //angka yang ingin di pangkatkan

                Input(pemangkat)                           //jumlah pemangkat

                hasil←angka

                for i ← 1 to pemangkat-1 do

                                hasil ←hasil *a

                endfor

                output(hasil)

operasi pengisian

Sintaks	Jumlah
Input(angka)	1
Input(pemangkat)	1
hasil←angka	1
for i ← 1 to pemangkat-1 do	n
hasil ←hasil *a	N
Total	3 + 2n

Operasi Perkalian

Sintaks	Jumlah
hasil ←hasil *a	N
Total	N

Operasi pengeluaran

Sintaks	Jumlah
output(hasil)	1
Total	1

TOTAL T(n)=CopC(n)

C(n)	Cop	T(n)
3 + 2n	A	(3 + 2n)a
n	B	(n)b
1	C	C

Total kebutuhan waktu eksekusi algoritma HitungRata2 :

Total Waktu = t1 + t2 + t3 = (3 + 2n)a + (n)b  + c

Luas_Permukaan_Kerucut

Deklarasi :

                Const

                Phi : 3.14

                r, t, v : real

Algoritma :

                Input (r)

                Input (t)

                V := phi * r * (r + t)

                Output (v)

Operasi Pengisian

Sintaks	Jumlah
Input(r)	1
Input(t)	1
V := phi * r * (r + t)	1
Jumlah	4

Operasi Aritmatika

Sintaks	Jumlah
phi * r	1
R* ( r+t)	1
R+t	1
Total	3

Operasi Pengeluaran

Sintaks	Jumlah
Output (v)	1
Total	1

TOTAL T(n)=CopC(n)

C(n)	Cop	T(n)
4	A	4a
3	b	3b
1	C	c

Total kebutuhan waktu eksekusi algoritma Luas Permukaan Kerucut :

Total Waktu = t1 + t2 + t3 = 4a + 3b + c