Kompleksitas Waktu dan Effisiensi Algoritma

Pada suatu algoritma yang perlu kita ketahui pada umumnya adalah:

Space, yaitu alokasi yang bersifat sintetis.
Struktur Program, berhubungan dengan berapa banyak langkah yang diperlukan untuk menjalankan algoritma yang dibuat
Rekursif, pemakaian fungsi rekursif atau perulangan pada suatu algoritma.

Kompleksitas waktu pada sebuah algoritma berisi jumlah langkah dan ekspresi bilangan yang dibutuhkan sebagai fungsi dari ukuran permasalahan. Kompleksitas ruang berkaitan dengan sistem memori yang dibutuhkan untuk eksekusi sebuah program. Tabel di bawah memperlihatkan kelompok algoritma berdasarkan kompleksitas waktu asimptotiknya.

kelompok algoritma berdasarkan kompleksitas waktu asimptotik

Efisiensi waktu algoritma

efisiensi waktu algoritma diukur dalam satuan n (problem size). terdapat 4 langkah untuk menentukan ukuran efisiensi waktu, antara lain:

Menentukan problem size (n)
Menentukan operasi dominan
Menentukan Fungsi langkah → g(n)
Menentukan kompleksitas waktu O(f(n)) (Big Oh function)

Menentukan Problem Size (n)

Menetukan Operasi Dominan

operasi dominan merupakan operasi yang paling banyak dilakukan, sesuai konteks permasalahan. misalkan pada algoritma menentukan nilai max/ min, operasi dominannya adalah operasi perbandingan ">" atau "<". pada algoritma searching operasi dominannya adalah operasi "=".

Menentukan Fungsi Langkah → g(n)

Menentukan kompleksitas waktu O(f(n)) (Big Oh function)

contoh:

tentukan g(n) dan Big Oh function dari algoritma di bawah ini:

k=n

while k> 0 do begin

for i=1 to n do

if(x>0) then ...

k=k div 2

end

Jawab: g(n) = n log n + 1 → O (n log n)

Contoh Kasus 1 Efisiensi Algoritma

Analisa

Bagian (a) di eksekusi 1 kali
Bagian (b) merupakan suatu loop, yang didasarkan atas kenaikan harga i dari i=1 hingga i=n. jadi statemen s=s+1 akan diproses sebanyak n kali sesuai kenaikan harga i
Bagian (c) akan diproses 1 kali
Karena bagian (b) merupakan bagian yang paling sering diproses, maka bagian (b) merupakan operasi aktif, sedangkan bagian (a) dan (c) dapat diabaikan karena jarang diproses.
Bagian (b) diproses sama dengan banyak data yang di masukkan (n).
Maka Algoritma penjumlahan bilangan rill tersebut mempunyai order sebanding dengan n atau memiliki Big Oh function = n atau O(n).

Contoh Kasus 2 (Belajar Kompleksitas Percabangan dan Looping dulu)