Minggu, 23 Oktober 2016

KOMPLEKASITAS ALGORITMA DALAM PENGGUNAAN "NOTASI"

Kompleksitas algoritma dalam penggunaanya terhadap "NOTASI" itu terdiri atas tiga notasi , yaitu :
  1. Notasi BIG O
  2. Notasi BIG THETA, dan
  3. Notasi BIG OMEGA
berikut kami akan membrikan beberapa contoh penyelesaian tentang mencari notasi BIG O, BIG THETA, dan BIG OMEGA sebagai berikut :

Algoritma cetak_angka ;

kamus
Angka,n : integer

algoritma
input (angka)
input (n)

i = 1 
While i ≤ n do
Write (angka)
i ← i+1
Endwhile

penyelesaiannya :



2n + 1

  • Big Omega

2n +1 ≥ 2n
n = 0                    1 ≥ 0
n = 1                    3 ≥ 2
n = 2                    5 ≥ 4

C = 2
n0= 0
n ≥ 0


  • Big O
2n + 1 ≤ 2n + n

n0= 1 ≤ 0
n1= 3 ≤ 3
n2= 5 ≤ 6

C = 2
n0= 2
n ≥ 2







  • Big Theta
  

2n + n ≥ 2n + 1 ≥ 2n
2n ≤ 2n +1 ≤ 2n + n


C = 2    n0 =2








Program menghitung_faktorial;

kamus
i,n,fak: integer;

algoritma
input <- (n)
fak <- 1;
for i := n downto 1 do 
fak:=fak*i;
endfor
  
output(n,fak)

penylesaiannya :



2n + 1

  • Big Omega

2n +1 ≥ 2n
n = 0                    1 ≥ 0
n = 1                    3 ≥ 2
n = 2                    5 ≥ 4

C = 2
n0= 0
n ≥ 0


  • Big O
2n + 1 ≤ 2n + n

n0= 1 ≤ 0
n1= 3 ≤ 3
n2= 5 ≤ 6

C = 2
n0= 2
n ≥ 2




  • Big Theta
  

2n + n ≥ 2n + 1 ≥ 2n
2n ≤ 2n +1 ≤ 2n + n


C = 2    n0 =2


Program bilangan_pangkat

Kamus
x, n, i, hasil : integer

Algoritma
x <- 2                                                     //bilangan yang akan dipangkatkan
n <- 3                                                     //pangkat dari bilangan yang akan dipangkatkan

                if n <- 0 then
                                hasil <- 1
                else
                                for i <- 1 to n do
                                                hasil <- hasil * x
                                endfor
                endif

output(hasil)



2n+1 = 2n = n

Penyelesaian :

  • Big Omega


n +1 ≥ n
n = 0                    1 ≥ 0
n = 2                    3 ≥ 2

C = 1
n0= 0
n ≥ 1

  • Big O

n + 1 ≤ n + n

n0 = 1 ≤ 0
n1= 2 ≤ 2
n2= 3 ≤ 4

C = 1
n0 = 1
n ≥ 1



  • Big Theta

  


n ≤ n +1 ≤ n + n


C = 2    n0 =2




Program _Pengulangan_bersarang

Kamus
                ulang 1, ulang 2, n : integer
Algoritma
                n <-  5
                                for ulang 1 <- 1 to n do
                begin
                                for ulang 2 <- 1 to n do
                                                write (‘A’)
Penyelesaian :

n2 + 1
  • Big Omega


n2 +1 ≥ n2
n = 0                    1 ≥ 0
n = 1                    2 ≥ 1
n = 2                    5 ≥ 4

C = 1
n0= 0
n ≥ 0

  • Big O

n2 + 1 ≤ n2

n0= 1 ≤ 0
n1= 2 ≤ 1
n2= 5 ≤ 4

C = 1
n0= 1
n ≥ 2

  • Big Theta  


n2 ≤ n2 +1 ≤ n2 + n


C = 1    n0 =2



Program_Cetak_angka  1-10

Kamus
i : Integer

Algoritma
                For i <- 1 to 10 do
                                Write (“,i)
Penyelesaian :


  • Big Omega


n  ≥ n – n
n = 0                    0 ≥ 0
n = 1                    1 ≥ 0
n = 2                    2 ≥ 0

C 1
n0 = 1
n ≥ 1

  • Big O

n  ≤ n - n

n0= 0 ≤ 0
n1= 1 ≤ 0
n2= 2 ≤ 0

C 1
n0 = 1
n ≥ 1



  • Big Theta

  

n-n ≤ n ≤ n + n


C = 1    n0 =1






Tidak ada komentar:

Posting Komentar