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)

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 Fungsi Langkah → g(n)


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

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

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)

Kompleksitas Waktu dan Effisiensi Algoritma


Contoh Kasus 3 (Belajar Kompleksitas Percabangan, Looping, Looping bersarang dulu)

Analisa Kompleksitas Waktu dan Effisiensi Algoritma Selection Sort

Analisa Kompleksitas Waktu dan Effisiensi Algoritma Selection Sort

Analisa Kompleksitas Waktu dan Effisiensi Algoritma Selection Sort




Kompleksitas Waktu dan Effisiensi Algoritma
MARKIJAR: MARi KIta belaJAR

Suka dengan artikel kami ? Tidak ada salahnya untuk berlangganan artikel terbaru dari MARKIJAR.Com langsung via email mu :

0 Response to "Kompleksitas Waktu dan Effisiensi Algoritma"

Post a Comment