BEST, WORST, dan AVERAGE

Untuk beberapa algoritma tertentu, kompleksitas waktu dibagi 3 :

-  Best – case efficiency [Tmin (n)]
    Kompleksitas dengan jumlah paling kecil.

-  Worst – case efficiency [Tmax (n)]
    Kompleksitas dengan jumlah paling besar.

-  Average – case efficiency [Tavg (n)]
    Kompleksitas dengan jumlah rata-rata keseluruhan kemungkinan.

Berikut ini beberapa contoh menghitung Tmax (n), Tmin (n), Tavg (n) :

1. Algoritma Mencari Elemen Max

procedure Mencari_Max(input a₁,...,a_n : integer, output max : integer)

Kamus:

   i,j : integer

Algoritma:

    max <-- a₁

    j <-- 2

    while (j <= n) do 

      if (a_j > max)

        then

          max <-- a_j

      endif

      i <-- i + 1

    endwhile
enprocedure

2. Algoritma Ganjil Genap

ganjil_genap

Kamus:

   bil, i,g1,g2,j1,j2,n : integer

   rt1,rt2 : real

Algoritma:     

    write(“Masukkan Banyaknya Data = “)

    input(n)

    for i <-- 1 to n  do

         write('Bilangan ke:',i ,' ')

         Input(bil) 

         if bil mod 2 = 0

         then        

              j1 <-- j1 +1

              g1 <-- g1+bil

         else

              j2 <-- j2+1

              g2 <-- g2+bil

         endif

    endfor

    rt1 <-- g1/j1

    rt2 <-- g2/j2

    write(“Jumlah bil. Ganjil= “)

    write(“Jumlah bil. Genap= “)

    write(“Rerata Ganjil= “)
    write(“Rerata Genap= “)  

3. Algoritma Binary Search

Procedure Binary_search(input a₁,...,a_n : integer, x : integer, output idx : integer)

Kamus:

   i, j, k : integer

   ketemu  : boolean

Algoritma:

    i <-- 1

    j <-- n

    ketemu <-- false

    while ( i <=  j) and (not ketemu)do

         k <-- (i + j) div 2  

         if (a_k = x)

      then

             ketemu <-- true

         else

           if (a_k < x)

        then  

               i <-- k + 1

           else   

               j <-- k - 1

           endif

         endif

    endwhile

    if (ketemu)

      then

        idx <-- k

      else

        idx <-- 0

    endif
endprocedure

4. Algoritma Segitiga Piramida

Segitiga_Piramida

Deklarasi

   n,kolom,I,j,m,c : integer

Algoritma

   input(n)

   kolom = (n*2)-1

 

   for i <-- 1 to n do

     for j <-- 1 to kolom do

           m = j-n

           if (m <= 0)

             then

               c <-- i + m

            else

               c <-- i – m

            endif

           if (c > 0)

             then

              output(“*”)

           else

              output(“ “)

           endif

           j <-- j+1

     endfor

     i <-- i + 1

   endfor

5. Algoritma Faktorial

faktorial   

Kamus:

   i, n, x    :integer

Algoritma:

    input(n)

    if (n<=0)

       then

           x <-- 1

       else

           x <-- 1

           for i <-- 2 to n do

           X <-- x*i

       endfor

     endif

     output(x)

Bagikan

Jangan lewatkan

BEST, WORST, dan AVERAGE

4/ 5

Oleh Rifaldi Yunus

Rifaldi Yunus 09.34 1 Komentar