Sabtu, 29 Oktober 2016

notasi asimtotik

3.Procedure banyak_suku
Deklarasi
  s  : real
 x,y,n :integer
Algoritma
 Input(n)
 s ←-1/3
 x ←1
 y ←3

for i ← 2 to N do
     X ← X * i
     y ← Y + i
    if (i mod 2 = 1) then
       S ← s - X/y
    else
       S ← s + X/Y
    endif
 endfor
    output('S = ')
 endprocedure

Langkah pertama cari cari t min (n), t max(n) dan t avg(n)nya berikut hasilnya

T min(n)=3+4=7
T max(n)=n+3
T avg(n)=3+n
                  n

Kemudian meghitung notasi  big oh, omega dan theta nya tiap T(n)
t min(n)=n
-Big oh(O)

T(n)≤O (g(n))
7≤1(1)
7≤2(2)
7≤3(3)
c=3
n0=n
-Big omega(Ω)
T(n)≥ Ω (g(n))
7 ≥ 1(1)
7 ≥2(2)
n0 =n
c =2

-big theta(θ)
 C2(g(n)) ≤ T(n) ≥ C1 (g(n))

batas atas


untuk t max
t max(n)=3n
-Big oh(O)
T(n)≤O (g(n))
7≤1(1)
7≤2(2)
7≤3(3)
n0 =n
c =3

-Big omega(Ω)
T(n)≥ Ω (g(n))
7 ≥ 1(1)
7 ≥ 2(2)

n0 =n
c =2

-big theta(θ)
 C1(g(n)) ≤ T(n) ≤ C2 (g(n))

batas atas
 C1(g(n)) ≤ T(n)
2n ≤ 7 ≤3n
n0 =n
c1 =3

batas bawah
 T(n) ≤ C2 (g(n))
2n≤7≤3n
 n0 =n
c2 =3


untuk t average

T avg(n)=3+n
                  n
t(n)=2n
-Big oh(O)
T(n)≤O (g(n))
7≤1(1)
7≤2(2)
7≤3(3)
n0 =n
c =3
-Big omega(Ω)
T(n)≥ Ω (g(n))
  7≥ 1(1)
7≥ 2(2)
n0 =2

c =2

-big theta(θ)
 C2(g(n)) ≤ T(n) ≤ C1 (g(n))

batas atas
 C2(g(n)) ≤ T(n)
2n ≤ 7 ≤3n
n0 =n
c1 =3

batas bawah
 T(n) ≤ C1 (g(n))
2n ≤ 7 ≤3n
 n0 =n
c2 =3

Tidak ada komentar:

Posting Komentar