Kompleksitas Algoritma : Waktu

Pada postingan ini kami akan membahas tentang Kompleksitas Waktu Algoritma, kita dapat mengukur waktu yang diperlukan oleh sebuah algoritma dengan menghitung banyaknya operasi/instruksi dasar yang dieksekusi.

Kita dapat menghitungnya dengan rumus berikut :

Berikut adalah beberapa contoh perhitungan kompleksitas waktu dalam suatu algoritma :

1.      Algoritma Pencarian Beruntun (Sequential Search)

Jumlah Operasi Dasar  :

Operasi Dasar	C(n)	Cop
<--	4+2n	a
<=	n+1	b
and	n+1	c
not	n+1	d
=	n	e
+	n	f

Perhitungan T(n) :

T(n) =  (4+2n)a + (n+1)b + (n+1)c + (n+1)d + (n)e + (n)f

2.      Algoritma Pencarian Bagidua (Binary Search)

Jumlah Operasi Dasar  :

Operasi Dasar	C(n)	Cop
<--	5+4n	a
not	n+1	b
and	n+1	c
<=	n+1	d
+	2n	e
div	n	f
=	n	g
<	n	h
-	n	i

Perhitungan T(n) :

T(n) = (5+4n)a + (n+1)b + (n+1)c + (n+1)d + (2n)e + (n)f + (n)g + (n)h + (n)i

3.      Algoritma Cari Elemen Terbesar

Jumlah Operasi Dasar  :

Operasi Dasar	C(n)	Cop
<--	2+2n	a
<=	n+1	b
>	n	c
+	n	d

Perhitungan T(n) :

T(n) = (2+2n)a + (n+1)b + (n)c + (n)d

4.      Algoritma Menghitung Rata-rata

Jumlah Operasi Dasar  :

Operasi Dasar	C(n)	Cop
input	1+n	a
<--	1+3n+2	b
+	n	c
/	n	d
output	1	e

Perhitungan T(n) :

T(n) = (1+n)a + (1+3n+2)b + (n)c + (n)d + e

5.      Algoritma Menghitung Volume Tabung

Jumlah Operasi Dasar  :

Operasi Dasar	C(1)	C(n)	Cop
<--	2	2n	a
input	2	2n	b
*	3	3n	c
output	1	n	d

Perhitungan T(n) :

T(1) = 2a + 2b + 3c + d

T(n) = (2n)a + (2n)b + (3n)c + (n)d