- Best Case : kompleksitas dengan jumlah paling kecil (Tmin)
- Worst Case : kompleksitas dngan jumlah paling besar (Tmax)
- Average Case : kompleksitas dengan jumah rata - rata keseluruhan kemungkinan
1. Mencari nilai tertinggi dan terendah di dalam array, diasumsikan elemen array sudah terisi
Procedure cari_maxmin (input a1,a2,a3,...,an : integer
, output max,min : integer)
{I.S.: array nilai ke-n sudah terdefinisi}
{F.S: menghasilkan nilai maximum dan minimum}
Kamus :
max,min
: integer
Algoritma :
input (n)
max ← a[1]
for i ← 2 to n do
max ← a[i]
else
if a[i]
<
min then
min ← a[i]
endif
endif
endfor
output
(max)
output
(min)
endprocedure
operator Utama
←
dari larik kedua, maka:
Tmax (n) = 3 + 2n -1
Tavg (n) = - Best Case
- Worst Case
dari larik kedua, maka:
Tmax (n) = 3 + 2n -1
- Average Case
2.
Procedure ipk(i1...in : real ; ipk : real)
{I.S. : user memasukan nilai ipk}
{F.S. : menghasilkan statemen}
Deklarasi
i1,i2,i3,i4,i5,i6,i7,i8,ipk : real
Algoritma
Ipk := i1+i2+i3+i4+i5+i6+i7+i8/8
If ipk > 3,0
Then
Output(nilai anda bagus)
Else
Output(nilai anda kurang)
Endif
:=
Tmin (n) = 3
Tmax (n) = n+2
Taverage (n) =
3+4+5+....+n+2
8
+
Tmin (n) = 6
Tmax (n) = 7
Taverage (n) = 6+5+4+...+7
8
3.
Procedure HitungRerataGanjil (Input a1, a2, …, an : integer, output rata_ganjil : real)
Procedure HitungRerataGanjil (Input a1, a2, …, an : integer, output rata_ganjil : real)
{I.S. : User memasukan bilangan bulat}
{F.S : Menampilkan hasil}
Deklarasi
{F.S : Menampilkan hasil}
Deklarasi
K: integer
Jumlah:
real
Algoritma
Input
(n)
k := 1
jumlah := 0
for
k := 1 to n do
if ak mod 2 = 1 then
jumlah := jumlah + ak
endif
endfor
rata_ganjil := jumlah/n
operator utama: +
Tmin(n) = 0
Tmax(n) = n
4.
PROGRAM TanggalBerikutnyaDiBulanFebruari
PROGRAM TanggalBerikutnyaDiBulanFebruari
{ Membaca sebuah tanggal pada bulan
Februari, kemudian menentukan tanggal keesokan harinya }
DEKLARASI:
type
tanggal : record <dd : integer,
mm: integer,
yy : integer
>
T :
tanggal
ALGORITMA :
T.mm
← 2 { bulan Februari }
read(T.dd,
T.yy) { baca komponen tanggal dan
tahun }
if T.dd < 28 then {
tidak ada masalah dengan tahun }
T.dd ← T.dd + 1 { tanggal besok }
else { T.dd 28 atau T.dd = 29 }
{
tanggal besok bergantung tahun kabisat/tidak }
if (T.yy mod 4 = 0 and T.yy mod 100
≠ 0) or
(T.yy
mod 400 = 0)) then {tahun kabisat}
if T.dd = 28 then
T.dd
← T.dd + 1 {29}
else {T.dd=29}
T.dd ← 1
T.mm ← T.mm +1
{bulan Maret}
end if
else { bukan
tahun kabisat, jadi sesudah 28 langsung tanggal 1}
T.dd ← 1 { tanggal 1 bulan Maret }
T.mm ← T.mm + 1
{ bulan Maret }
end if
end if
write(T.dd,
T.mm, T.yy) { cetak tanggal besok }
General
Plan for Analyzing the Time Efficiency of Nonrecursive Algorithms
1.
Menentukan
parameter mengindikasikan besar/jumlah input
2.
Mengidentifikasi
Operasi Dasar Algoritma (sesuai aturan yang berapa pada bagian terdalam
loop/perulangan)
3.
Cek apakah
beberapa operasi dasar (yang ditentukan pada nomer 2) tersebut dieksekusi hanya
pada jumlah input. Jika tidak Worst Case, Avarage case, Best Case dihitung
secara terpisah
4.
Tentukan jumlah
dari operasi dasar yang dieksekusi
5.
Menggunakan
formula standart dan hokum manipulasi penjumlahan. Apakah penghitungan mencari dengan form formula tertutup, atau
paling tidak membuat “order of growth”nya
1.
Parameter Input
dari algoritma adalah tanggal (T) yaitu T.dd, T.mm, T.yy
2.
Bagian terdalam
loop
if T.dd = 28 then
T.dd ← T.dd + 1 {29}
else {T.dd=29}
T.dd
← 1
T.mm ← T.mm +1 {bulan Maret}
end
if
Operasi
Dasar pada perulangan terdalam yang terbanyak adalah assignment (←)
Keseluruhan
assignment pada algoritma sebanyak 6x
Assignment
pada algoritma terdalam 3x
Maka
Best Case dari algoritma di atas Tmin(n) = 1 (langsung ditemukan tanpa perulangan)
Best Case dari algoritma di atas Tmin(n) = 1 (langsung ditemukan tanpa perulangan)
Worst
Case dari algoritma di atas Tmax(n)= T(2n)/T(n)
=
Cop.C(2n)/Cop.C(n)
=
C(2n)/C(n)
=2(3n)+6/3n+6
=6n+12/3n+6 ←12, 6(12, 6. ‘n’pangkat nol)
=6n/3n ← yg digunakan pangkat
tertinggi
=2
Avarage Case Tavg(n) =3n+6/n
5.
Procedure PencarianBeruntun(input a1, a2, ..., an : integer, x : integer, output idx : integer)
{I.S. : User memasukan bilangan}
{F.S. : Menampilkan output}
Deklarasi
k : integer
ketemu : boolean
Algoritma
k ← 1
ketemu ← false
while (k <= n) and (not ketemu) do
if ak = x then
ketemu ← true
else
k ← k + 1
endif
endwhile
{ k > n or ketemu }
if ketemu then
idx ← k
else
idx ← 0
endif
Tmin(n) = 1
Tmax(n) = n
Tavg(n) =
0 komentar:
Posting Komentar