Kompleksitas Algoritma : Notasi Asimtotik

1.Algoritma Perkalian Matriks

procedure kalimatrik(input matriks1, matriks2 : data)

Deklarasi

  hasil : data

  i,j,z : integer

Algoritma

  for i <- 1 to baris do

    for j <- 1 to kolom do

    begin

      hasil[i,j] <- 0

      for <- 1 to baris do

        hasil[i,j] <- hasil[i,j] + matrikI[i,z] * matrikII[z,j]

      endfor

    endfor

  endfor

  write('Hasil Perkalian MATRIK');

  for i <- 1 to baris do

    for <- 1 to kolom do

    begin

      write(hasil[i,j])

    endfor

  endfor

Operasi Dasar :

Operasi Dasar

<-

+

*

Write

output

Operasi Penting :

<-

Notasi Asimtotik :

·         Tmin(n)     = 7n

Big O

T(n) =	7n		€	O (n2)			n  >=  n0
	T(n)		<=	C.g(n)			n  >=  4
	7n		<=	2 n2			n0  =   4
n = 0	0		<=	0	Salah		C   =   2
n = 1	7		<=	2	Salah
n = 2	14		<=	8	Salah
n = 3	21		<=	18	Salah
n = 4	28		<=	32	Benar
n = 10	70		<=	200	Benar
n = 100	700		<=	20000	Benar

Big Omega

T(n) =	7n	€	Ω (n)			n  >=  n0
	7n	>=	n			n  >=  0
n = 0	0	>=	0	Benar		n0  =   0
n = 1	7	>=	1	Benar		C   =   1
n = 2	14	>=	4	Benar
n = 3	21	>=	9	Benar
n = 10	70	>=	10	Benar
n = 100	700	>=	100	Benar

Big Theta

·         Tmax(n)     = 7n

Big O

T(n) =	7n		€	O (n2)			n  >=  n0
	T(n)		<=	C.g(n)			n  >=  4
	7n		<=	2 n2			n0  =   4
n = 0	0		<=	0	Salah		C   =   2
n = 1	7		<=	2	Salah
n = 2	14		<=	8	Salah
n = 3	21		<=	18	Salah
n = 4	28		<=	32	Benar
n = 10	70		<=	200	Benar
n = 100	700		<=	20000	Benar

Big Omega

T(n) =	7n	€	Ω (n)			n  >=  n0
	7n	>=	n			n  >=  0
n = 0	0	>=	0	Benar		n0  =   0
n = 1	7	>=	1	Benar		C   =   1
n = 2	14	>=	4	Benar
n = 3	21	>=	9	Benar
n = 10	70	>=	10	Benar
n = 100	700	>=	100	Benar

Big Theta

·         Tavg(n)      = (7n+1)/2

Big O

T(n) =	(7n+1)/2	€	O (n2)			n  >=  n0
	T(n)	<=	C.g(n)			n  >=  3
	7n+1/2	<=	2 n2			n0  =   3
n = 0	1/2	<=	0	Salah		C   =   2
n = 1	4	<=	2	Salah
n = 2	15/2	<=	6	Salah
n = 3	11	<=	18	Benar
n = 10	71/2	<=	200	Benar
n = 100	701/2	<=	20000	Benar

Big Omega

T(n) =	(7n+1)/2	€	Ω (n)			n  >=  n0
	7n+1/2	>=	n			n  >=  0
n = 0	1/2	>=	0	Benar		n0  =   0
n = 1	4	>=	1	Benar		C   =   1
n = 2	15/2	>=	2	Benar
n = 3	11	>=	3	Benar
n = 10	71/2	>=	10	Benar
n = 100	701/2	>=	100	Benar

Big Theta

2.Algoritma Nilai Ujian

 Program nilai_ujian

Deklarasi
  nama  : string [20]
  nilai : integer

Algoritma

  input (nama)
  input (nilai)

  if (nilai >= 90) and (nilai <= 100) then
    output('Selamat Anda Lulus Dengan Nilai A')
  else if (nilai >= 70) and (nilai <= 89) then
    output('Selamat Anda Lulus Dengan Nilai B’)

  else if (nilai >= 60) and (nilai <= 69) then
    output('Selamat Anda Lulus Dengan Nilai C’)
  else
    output('Maaf Anda Gagal Dalam Ujian Ini')

Operasi Dasar :

Operasi Dasar

input

>=

<=

and

output

Operasi Penting :

and

Notasi Asimtotik :

·         Tmin(n)     = n

Big O

T(n) =	n		€	O (n2)			n  >=  n0
	T(n)		<=	C.g(n)			n  >=  0
	n		<=	n2			n0  =   0
n = 0	0		<=	0	Benar		C   =   1
n = 1	1		<=	1	Benar
n = 2	2		<=	4	Benar
n = 10	10		<=	100	Benar
n = 100	100		<=	10000	Benar

Big Omega

T(n) =	n	€	Ω (n)			n  >=  n0
	n	>=	1/2 n			n  >=  0
n = 0	0	>=	0	Benar		n0  =   0
n = 1	1	>=	½	Benar		C   =   1/2
n = 2	2	>=	1	Benar
n = 10	10	>=	5	Benar
n = 100	100	>=	50	Benar

Big Theta

·         Tmax(n)     = n

Big O

T(n) =	n		€	O (n2)			n  >=  n0
	T(n)		<=	C.g(n)			n  >=  0
	n		<=	n2			n0  =   0
n = 0	0		<=	0	Benar		C   =   1
n = 1	1		<=	1	Benar
n = 2	2		<=	4	Benar
n = 10	10		<=	100	Benar
n = 100	100		<=	10000	Benar

Big Omega

T(n) =	n	€	Ω (n)			n  >=  n0
	n	>=	1/2 n			n  >=  0
n = 0	0	>=	0	Benar		n0  =   0
n = 1	1	>=	½	Benar		C   =   1/2
n = 2	2	>=	1	Benar
n = 10	10	>=	5	Benar
n = 100	100	>=	50	Benar

Big Theta

·         Tmax(n)     = (n+1)/2

Big O

T(n) =	(n+1)/2		€	O (n)			n  >=  n0
	T(n)		<=	C.g(n)			n  >=  1
	(n+1)/2		<=	n			n0  =   1
n = 0	½		<=	0	Salah		C   =   1
n = 1	1		<=	1	Benar
n = 2	3/2		<=	4	Benar
n = 10	11/2		<=	10	Benar
n = 100	101/2		<=	100	Benar

Big Omega

T(n) =	(n+1)/2	€	Ω (n)			n  >=  n0
	(n+1)/2	>=	1/2 n			n  >=  0
n = 0	0	>=	0	Benar		n0  =   0
n = 1	1	>=	½	Benar		C   =   1/2
n = 2	3/2	>=	1	Benar
n = 10	11/2	>=	5	Benar
n = 100	101/2	>=	50	Benar

Big Theta

3.Algoritma Bilangan Prima

 program prima

Deklarasi

  i,bil,p : byte

Algoritma

  p <- 0

  input(bil)

  for i <- 1 to bil do

  begin

    if bil mod i = 0 then

      p <- p+1

  endfor

  if p = 2 then

    output(bil,' Bilangan Prima')

  else

    output(bil,' Bukan Bilangan Prima')

Operasi Dasar :

Operasi Dasar

<-

mod

=

+

output

Operasi Penting :

+

Notasi Asimtotik :

·         Tmin(n)     = n

Big O

T(n) =	n		€	O (n2)			n  >=  n0
	T(n)		<=	C.g(n)			n  >=  0
	n		<=	n2			n0  =   0
n = 0	0		<=	0	Benar		C   =   1
n = 1	1		<=	1	Benar
n = 2	2		<=	4	Benar
n = 10	10		<=	100	Benar
n = 100	100		<=	10000	Benar

Big Omega

T(n) =	n	€	Ω (n)			n  >=  n0
	n	>=	1/2 n			n  >=  0
n = 0	0	>=	0	Benar		n0  =   0
n = 1	1	>=	½	Benar		C   =   1/2
n = 2	2	>=	1	Benar
n = 10	10	>=	5	Benar
n = 100	100	>=	50	Benar

Big Theta

·         Tmax(n)     = 2n+1

Big O

T(n) =	2n+1		€	O (n2)			n  >=  n0
	T(n)		<=	C.g(n)			n  >=  3
	2n+1		<=	n2			n0  =   3
n = 0	1		<=	0	Salah		C   =   1
n = 1	3		<=	1	Salah
n = 2	5		<=	4	Salah
n = 3	7		<=	9	Benar
n = 10	21		<=	100	Benar
n = 100	201		<=	10000	Benar

Big Omega

T(n) =	2n+1	€	Ω (n)			n  >=  n0
	2n+1	>=	1/2 n			n  >=  0
n = 0	0	>=	0	Benar		n0  =   0
n = 1	1	>=	½	Benar		C   =   1/2
n = 2	2	>=	1	Benar
n = 10	21	>=	5	Benar
n = 100	201	>=	50	Benar

Big Theta

·         Tavg(n)      = (2n+1)/2

Big O

T(n) =	(2n+1)/2		€	O (n2)			n  >=  n0
	T(n)		<=	C.g(n)			n  >=  2
	(2n+1)/2		<=	n2			n0  =   2
n = 0	½		<=	0	Salah		C   =   1
n = 1	3/2		<=	1	Salah
n = 2	5/2		<=	4	Benar
n = 3	7/2		<=	9	Benar
n = 10	21/2		<=	100	Benar
n = 100	201/2		<=	10000	Benar

Big Omega

T(n) =	(2n+1)/2	€	Ω (n)			n  >=  n0
	(2n+1)/2	>=	n			n  >=  0
n = 0	0	>=	0	Benar		n0  =   0
n = 1	3/2	>=	1	Benar		C   =   1
n = 2	5/2	>=	2	Benar
n = 10	21/2	>=	10	Benar
n = 100	201	>=	100	Benar

Big Theta

4.Algoritma Grade Nilai

 program CetakSegitigaBintang

{mencetak segitiga bintang dengan tinggi = n}

Deklarasi

  n,i,j: integer

Algoritma

  read(n)

  {cetak bagian segitiga dari baris 1 sampai n}

  for i <- 1 to n do

    for j <- 1 to i

      write(‘*’)

    endfor

  endfor

  {Cetak bagian yang merupakan pencerminan dari setengah segitiga

  pertama}

  for i <- n-1 downto 1 do

    for j <- to i do

      write(‘*’)

    endfor

  endfor

Operasi Dasar :

Operasi Dasar

<-

output

-

Operasi Penting :

<-

Notasi Asimtotik :

·         Tmin(n)     = 4n+1

Big O

T(n) =	4n+1		€	O (n2)			n  >=  n0
	T(n)		<=	C.g(n)			n  >=  1
	4n+1		<=	5 n2			n0  =   1
n = 0	1		<=	0	Salah		C   =   5
n = 1	5		<=	5	Benar
n = 2	9		<=	20	Benar
n = 10	41		<=	500	Benar
n = 100	401		<=	50000	Benar

Big Omega

T(n) =	4n+1	€	Ω (n)			n  >=  n0
	4n+1	>=	n			n  >=  0
n = 0	0	>=	0	Benar		n0  =   0
n = 1	5	>=	1	Benar		C   =   1
n = 2	9	>=	2	Benar
n = 10	41	>=	10	Benar
n = 100	401	>=	100	Benar

Big Theta

·         Tmax(n)     = 4n+1

Big O

T(n) =	4n+1		€	O (n2)			n  >=  n0
	T(n)		<=	C.g(n)			n  >=  1
	4n+1		<=	5 n2			n0  =   1
n = 0	1		<=	0	Salah		C   =   5
n = 1	5		<=	5	Benar
n = 2	9		<=	20	Benar
n = 10	41		<=	500	Benar
n = 100	401		<=	50000	Benar

Big Omega

T(n) =	4n+1	€	Ω (n)			n  >=  n0
	4n+1	>=	n			n  >=  0
n = 0	0	>=	0	Benar		n0  =   0
n = 1	5	>=	1	Benar		C   =   1
n = 2	9	>=	2	Benar
n = 10	41	>=	10	Benar
n = 100	401	>=	100	Benar

Big Theta

·         Tavg(n)      = (4n+1)/2

Big O

T(n) =	(4n+1)/2		€	O (n2)			n  >=  n0
	T(n)		<=	C.g(n)			n  >=  1
	(4n+1)/2		<=	n2			n0  =   1
n = 0	½		<=	0	Salah		C   =   1
n = 1	5/2		<=	1	Benar
n = 2	9/2		<=	4	Benar
n = 10	41/2		<=	100	Benar
n = 100	401/2		<=	10000	Benar

Big Omega

T(n) =	(4n+1)/2	€	Ω (n)			n  >=  n0
	(4n+1)/2	>=	n			n  >=  0
n = 0	0	>=	0	Benar		n0  =   0
n = 1	5/2	>=	1	Benar		C   =   1
n = 2	9/2	>=	2	Benar
n = 10	41/2	>=	10	Benar
n = 100	401	>=	100	Benar

Big Theta

5.Algoritma Jenis Bilangan Bulat

 program jenis_bilbul

{menentukan apakah sebuah bilangan bulat merupakan bilangan positif, negatif, atau nol}

Deklarasi

  x:integer

Algoritma

  read(x)

  if x > 0 then

    output('Positif')

  else if x < 0 then

    output('Negatif')

  else if x = 0 then

    output('Nol')

  endif

Operasi Dasar :

Operasi Dasar

<-

>

<

output

=

Operasi Penting :

output

Notasi Asimtotik :

·         Tmin(n)     = n

Big O

T(n) =	n		€	O (n2)			n  >=  n0
	T(n)		<=	C.g(n)			n  >=  0
	n		<=	n2			n0  =   0
n = 0	0		<=	0	Benar		C   =   1
n = 1	1		<=	1	Benar
n = 2	2		<=	4	Benar
n = 10	10		<=	100	Benar
n = 100	100		<=	10000	Benar

Big Omega

T(n) =	n	€	Ω (n)			n  >=  n0
	n	>=	1/2 n			n  >=  0
n = 0	0	>=	0	Benar		n0  =   0
n = 1	1	>=	½	Benar		C   =   1/2
n = 2	2	>=	1	Benar
n = 10	10	>=	5	Benar
n = 100	100	>=	50	Benar

Big Theta

·         Tmax(n)     = n

Big O

T(n) =	n		€	O (n2)			n  >=  n0
	T(n)		<=	C.g(n)			n  >=  0
	n		<=	n2			n0  =   0
n = 0	0		<=	0	Benar		C   =   1
n = 1	1		<=	1	Benar
n = 2	2		<=	4	Benar
n = 10	10		<=	100	Benar
n = 100	100		<=	10000	Benar

Big Omega

T(n) =	n	€	Ω (n)			n  >=  n0
	n	>=	1/2 n			n  >=  0
n = 0	0	>=	0	Benar		n0  =   0
n = 1	1	>=	½	Benar		C   =   1/2
n = 2	2	>=	1	Benar
n = 10	10	>=	5	Benar
n = 100	100	>=	50	Benar

Big Theta

·         Tavg(n)      = (n+1)/2

·         Big O

T(n) =	(n+1)/2		€	O (n)			n  >=  n0
	T(n)		<=	C.g(n)			n  >=  1
	(n+1)/2		<=	n			n0  =   1
n = 0	½		<=	0	Salah		C   =   1
n = 1	1		<=	1	Benar
n = 2	3/2		<=	4	Benar
n = 10	11/2		<=	10	Benar
n = 100	101/2		<=	100	Benar

·         Big Omega

T(n) =	(n+1)/2	€	Ω (n)			n  >=  n0
	(n+1)/2	>=	1/2 n			n  >=  0
n = 0	0	>=	0	Benar		n0  =   0
n = 1	1	>=	½	Benar		C   =   1/2
n = 2	3/2	>=	1	Benar
n = 10	11/2	>=	5	Benar
n = 100	101/2	>=	50	Benar

·         Big Theta

Read More