Mencari Notasi Asimtotik

Algoritma Sequential search

procedure pencarianberuntun (input a1, a2, ...., an : integer . x  : integer , output idx : integer)

Deklarasi

   k : integer

   ketemu : bolean     (bernilai true jika x di temukan atau false jika x ditemukan )

Algoritma:

    k <-- 1

    ketemu  <-- false

    while (k < n ) and (not ketemu)

        if ak = x then ketemu <-- true 

        else k <-- k +1 

        endif

    endwhile

    {k > n or ketemu }

    if ketemu then idx <-- 0 {x di temukan }

    else idx <-- 0 {x tidak ditemukan }

    endif

Menghitung Tmin , Tmax ,Tavg

kasus terbaik : terjadi bila a1 = x

Tmin(n) = 1

Kasus terburuk : bila an =x atau x tidak ditemukan

Tmax(n) = n

Kasus rata-rata : jika x ditemukan pasa posisi ke-k , maka operasi  perbandingan (ak = x ) akan di eksekusi sebanyak k kali

Tavg(n) = (1+ 2+..n)  = n+1

             n         2

Menghitung T(n)

 T(Min) : 1

 T(Max) : n

Operasi Dasar	Cop	C(n)
<        = 1  >       = 1         =         = 1          ←         = 5n+1	a b c d	1na 1nb 1nc (5n+1)d

T(n) = Cop . C(n)

        = (1na) + (1nb) + (1nc) (5n+1)d

T(avg) = 1na + 2nb + 1nc + (5n+1)d  = n

                            n

MENCARI  NOTASI ASIMTOTIK
  O                                                       (Oh) 

(Omega)

 (Theta)

For-Endfor T(max) : n

Big O(Oh)

T(min) :  n    €    O(n)

          n    ≤    n

         _________________

         No : 0    C : 1

N = 0     n    ≤    0    √

N = 100   n    ≤    n    √

Big (Omega)

T(min) :  n    €    (n)

          n    ≥    n

          _________________

          No : 0       C : 1

N = 0     n    ≤    0    √

N = 100   n    ≤    n    √

Big (Theta)

T(min) :  n    €    (n)

          n   ≤    n    ≥    n

          ______________________

          No : 0         C : 1

Batas atas : O(n)

      

     T(n) : 1n    ≤    1n²    ≥    1n²

Batas bawah  (n)

     1n  = 1n

     C1 = 1, C2 = 1, No = n

If-Endif T(min) : 1

Big O(Oh)

T(min) :  1    €    O(n)

          1    ≤    1n

          _________________

          No : 1   C : 1n

N = 0     1    ≤    0   x

N = 100   10   ≤    100  x

Big (Omega)

T(min) :  1    €    (n)

          1    ≥    1n

          _________________

          No : 1      C : 1n

N = 0     1    ≥    0    √

N = 100   1    ≥    100  x

Big (Theta)

T(min) :  1    €    (n)

          1   ≤    1n    ≥    1

          _______________________

          No : 0           C : 1n

Batas atas : O(n)

      

     T(n) : 1n    ≤    1n²    ≥    1n²

Batas bawah  (n)

     1n  = 1n²

     C1 = 1, C2 = 1, No = 1n²

If-Endif T(max) : 2

Big O(Oh)

T(Max) :  2    €    O(n²)

          2    ≤    1n²

          _________________

          No : 2   C : 1n²

N = 0     2    ≤    0   √

N = 100   10   ≤    100  x

Big (Omega)

T(Max) :  2    €    (n²)

          1    ≥    1n

          _________________

          No : 2      C : 1n²

N = 0     2    ≥    0    √

N = 100   2    ≥    100  x

Big (Theta)

T(Max) :  2    €    (n²)

          2    ≤    1n²    ≥    1

          _______________________

          No : 2          C : 1n²

Batas atas : O(n²)

      

     T(n) : 2n    ≤    2n²    ≥    1n²

Batas bawah  (n)

     2n  = 1n²

     C1 = 2, C2 = 1, No = 1n²

T(AVG):(n+1)

               2       ~

Big O(Oh)

T(avg) :  :n+1 ~  n €    O(n²)

         2         ~

                 

          :n+1~  n ≤    1n²

         2            ~

    

          No : 1+2+3 =  5d : 1

N = 0     5    ≤    0   x

N = 100   0    ≤    1 √

Big (Omega)

T(avg) :  5    €    (n²)

          5    ≥    1n

          _________________

          No : 7      C : 1

N = 0     5    ≥    0    √

N = 100   5    ≥    100  x

Big (Theta)

T(avg) :  5    €    (n²)

          5   ≤    1n²    ≥    1

          _______________________

          No : 5          d : 1

Batas atas : O(n²)

      

     T(n) : 5n(n-1)    ≤    5n²-5n    ≥    5n²

                  

Batas bawah  (n)

     5n  = 5n²

     d1 = 5, d2 = 5, No = 5n²

Mencari Rumus T(n) Dari Procedure Rata-rata

PSEDUCODE RATA-RATA


Procedure Rata_Rata (input Total, Nilai : integer)-> Real

Deklarasi 

 {Tidak ada }

Algoritma

     rata_rata <-- Total / N

endfunction

input (nilai)
Total <-- 0
for i <-- 1 to N do
   input ( mhs(i).Nim , Mhs(i).Nama ,Mhs(i).Nilai )
   Mhs(i).indeks <-- indeks_nilai ( Mhs(i).Nilai )
   Output ( Mhs(i).indeks )
   Total <-- total + Mhs(i).Nilai

endfor

    Output('Rata-rata Nilai     :', rata_rata(Total,N))
    Otuput('Nilai Tertinggi     :', Nilai_max(Mhs,N))

Function Nilai_max (input Mhs : mahasiswa, input N : integer) --> integer

Deklarasi 

  max,i : integer;

Algoritma

max <-- Mhs(i).Nilai
for i <-- 2 to N do
  if (Mhs(i).Nilai > max)
     then
        max<-- Mhs(i).Nilai

  endif
endfor
Nilai_max <-- max
endfunction

Menghitung Tmin, Tmax, Tavg


OPERASI DASAR

            <--
              >
              *
              +
               /

Operasi Paling Dalam
            <--

Tmin(n) = 1+2 = 3
Tmax(n) = N+2
Tavg(n)  = 3+4+5+....(n+2) ~~ n

                           n

O (Big Oh)	Ω (Big Omega)	Θ (Big Theta)
Tmin (n) = 3	Tmin (n) = 3	Tmin (n) = 3
O = t(n) € O (g(n)); t(n) ≤ Cg(n)	Ω = t(n) € O (g(n)); t(n) ≤ Cg(n)	Θ = t(n) € Θ (g(n)); C2g(n) ≤ t(n) ≤ C1g(n)
Tmin(n) = 3 € O (1)	Tmin(n) = 3 € Ω (1)	Batas Atas = 3 € O (1)
no = 0	no = 0	Batas Bawah = 3 € Ω (1)
C = 1	C = 1	Jadi = no = 0
		C1 = 1, C2 = 1

Tmax = n+2

O (Big Oh)

O = t(n) € O (g(n)); t(n) ≤ Cg(n)
       n+2 € O(n)

n+2 ≤ 2n

2   ≤   0       n = 0      (x)
5   ≤   6       n = 3      (√)
11  ≤   18       n =  9        (√)
22  ≤   40       n =  20      (√) 

Jadi no = 3
         C  = 2


Ω (Big Omega)

Ω = t(n) € O (g(n)); t(n) ≤ Cg(n)
       n+2 € Ω (n)
       n+2 > n

2     >   0           n = 0      (√)
6      >    0              n = 4         (√)
10    >    0              n = 8         (√)
102  >    0              n = 100    (√)

Jadi no = 0   
C = 1



O (Big Theta)

Θ = t(n) € Θ (g(n)); C2g(n) ≤ t(n) ≤ C1g(n)
Batas Atas = n+2 < 2n = no = 3, C1 = 2
Batas Bawah = n+2 > n= no = 0, C2 = 1
Jadi no= 3, C1= 2, C2 = 1


Tavg(n)  3+4+5+......(n+2)
                          n
            = 1/2 n (3+(n+2))/n
            = 1/2(n+5)
            = n/2 + 5/2 
            = 1/2 + 5/n


          

O (Big Oh)

O = t(n) € O (g(n)); t(n) ≤ Cg(n)
       1/2n + 5/2 € O(n)

1/2n + 5/2  ≤ 2n

5/2   ≤  0       n = 0      (x)
5/2   ≤ 12      n = 6      (√)
5/2   ≤   18      n =  9        (√)
5/2   ≤   90      n =  30      (√) 

Jadi no =6
         C  = 2



Ω (Big Omega)

Ω = t(n) € O (g(n)); t(n) ≤ Cg(n)
       1/2 + 5/2 € Ω (n)
       1/2 + 5/2 > n

5/2       >   0           n = 0      (√)
6/2        >    1              n = 1        (√)
9/2        >    4              n = 4        (√)
95/2      >    90            n = 90      (x)
105/2    >    100          n = 100   (x)

Jadi no = 0   
C = 1



O (Big Theta)

Θ = t(n) € Θ (g(n)); C2g(n) ≤ t(n) ≤ C1g(n)
Batas Atas = 1/2n + 5/2 < 2n
Jadi no = 6, C1 = 2
Batas Bawah = 1/2n + 5/2 > 2
Jadi no= 0, C2= 1
Jadi no =6, C1 = 2, C2=1