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²