kompleksitas algoritma

Strategi Algoritma Kuliah 2 : Kompleksitas AlgoritmaE. Haodudin NurkifliTeknik InformatikaUniversitas Ahmad Dahlan

Jenis algoritmaDivide and conquer : menyederhanakan problem yang besar.Greedy methode : mencari yang optimal pada saat itu.

Algoritma : jumlah langkah yang berhingga (finite) instruksinya jelas Contoh : for i do 10 then .....

Tujuan Menganalisis algoritma Efisiensi waktu Efisiensi storage

Analisis algoritma Menentukan karakteristik kinerja (memprediksi sumber daya)Mengapa ?

Memilih algoritma yang paling efisien dari beberapa alternatif penyelesaian untuk kasus yang sama Mencari waktu yang terbaik untuk keperluan praktisApakah algoritma itu optimal untuk beberapa kasus atau ada yang lebih baik

Runing time fungsi dari input sizeMemanggil instruksi sederhana dan mengakses ke memory word sebagai primitive operation atau stepJumlah step eksekusi algoritma pada input tersebut Dikenal juga complexity and input

Kompleksitas tergantungUkuran input bergantung pada problem

Misalkan jumlah data yang diurutkanKarakter lain dari input

Apakah data sudah terurutApakah ada lingkaran dalam grafik

KompleksitasWorst-case : kompleksitas waktu untuk waktu terburuk (waktu tempuh bernilai maksimum dari suatu fungsi f(n)) atau Tmax(n)Best-case : kompleksitas waktu untuk waktu terbaik (kompleksitas waktu yang bernilai minimum dari suatu fungsi f(n)) atau Tmin(n)Average-case : kompleksitas waktu untuk kasus rata-rata

Metode AnalisisAsymptotic/theoretic/mathematic : berdasarkan pendekatan secara teori atau atas dasar analisa secara matematikEmpirical/Practical/Empiris/Praktis : berdasarkan pendekatan praktis yang biasanya didasarkan atas data-data yang telah ada atau data-data yang di-generete / dibangkitkan

AsymptoticMenggambarkan karakteristik/perilaku suatu algoritma pada batasan tertentu (berupa suatu fungsi matematis)Dituliskan dengan notasi matematis yg dikenal dgn notasi asymptotic Notasi asymptotic dapat dituliskan dengan beberpa simbul berikut

Q, O, W, o, w

Q, O, W, o, wDidefinisikan untuk fungsi diatas nilai biasaContoh: f(n) = Q(n2).Menggambarkan bagaimana fungsi f(n) tumbuh pd pembandingan untuk n2.Mendefinisikan himpunan fungsi ; Pada prakteknya untuk membandingan 2 ukuran fungsi.Notasi menggambarkan perbedaan rate-of-growth hubungan antara definisi fungsi dan definisi himpunan fungsi.

Notasi Asymptotic

Notasi O (big Oh)Untuk fungsi g(n),kita definisikan O(g(n)) sbg big-Oh dari n, sbg himpunan:O(g(n)) = {f(n) : konstanta positif c dan n0, sedemikian rupa n n0, sehingga 0 f(n) cg(n) }Ada konstanta n : ada, : untuk semua

Lanjtf(n) Secara intuitif : himpunan seluruh fungsi yg rate of growth nya adalah sama atau lebih kecil dari g(n).g(n) adalah asymptotic upper bound untuk f(n).f(n) = (g(n)) f(n) = O(g(n)).(g(n)) O(g(n)).

Lanjt2.99 = 2.50 =2.0001 = 3n + 7 = ? (tidak bakal lebih 4n)2n2 + 5 = ?

Big Oh O adalah merupakan Upper bound dari suatu fungsi

3 (pembulatan ke atas dalah 3)33

LanjtSehingga dari f(n) = 3n+4akan terpenuhi f(n) = 4berarti f(n)=O(4n) untuk n0=4n

Contoh dan LatihanApa fungsi big Oh dari

4n ?2n+7 ?

n2 ?n2+3 ?

Notasi (big Omega)(g(n)) = {f(n) : konstanta positif c dan n0, sedemikian hingga n n0, maka 0 cg(n) f(n)}Untuk fungsi g(n),kita definisikan (g(n)) sbg big-Omega dari n, sbg himpunan:

Lanjtg(n) adalah asymptotic lower bound untuk f(n).f(n) = (g(n)) f(n) = (g(n)). (g(n)) (g(n)).f(n) Secara intuitif : himpunan dari semua nilai fungsi yang rate of growth-nya adalah sama atau lebih tinggi dari g(n).

Lanjt2.0001 =2.50 =2.99 =3n + 7 = 2n2 + 5 =

Big Omega adalah merupakan Lower bound dari suatu fungsi

2 (batas bawah tidak akan kurang dari 2)22??

Notasi (big theta)Untuk fungsi g(n),kita definisikan (g(n)) sbg big-theta dari n, sbg himpunan sprt berikut(g(n)) = {f(n) : konstanta positif c1, c2 dan n0, sedmikian rupa n n0, maka 0 c1g(n) f(n) c2g(n)}

LanjtBig theta adalah merupakan tight bound dari suatu fungsi

f(n) merupakan (g(n))pada nilai antara c1 smp c2g(n) adalah asymptotically tight bound untuk f(n).

LanjtSecara intuitif : himpunan seluruh fungsi yang rate of growth-nya sama dengan g(n).Secara teknik, f(n) (g(n)).Penggunan sebelumnya, f(n) = (g(n)).Mana yg akan kita teima ?f(n) dan g(n) nonnegative, untuk nilai n besar.

Contoh(g(n)) = {f(n) : konstanta positif c1, c2, dan n0, yg mana n n0, 0 c1g(n) f(n) c2g(n)}10n2 - 3n = (n2)Apa nilai konstanta n0, c1, dan c2 sehingga akan terpenuhi fungsi tsb?Buat c1 sedkit lebih kecil dari koefisien utama, dan c2 sedikit lebih besar.Untuk membandingkan tingkat pertumbuhan, lihat term utama.Latihan: Buktikan bahwa n2/2-3n = (n2)

Relasi antara Q, O, W

Relasi antara Q, O, WTeorema : untuk 2 fungsi g(n) dan f(n), f(n) = (g(n)) jika f(n) = O(g(n)) dan f(n) = (g(n)).yakni, (g(n)) = O (g(n)) W (g(n))Dalam prakteknya, nilai (atau tight bounds) didapat dari asymptotic upper bound dan lower bound.

Running TimeRunning time dari suatu algoritma, secara matematis adalah suatu fungsi input n untuk sejumlah n dataMisal f(n)=n2 berarti fungsi runing time dari sejumlah n data adalah n2 Running time merupakan fungsi kebutuhan sumberdaya yang diperlukan suatu algoritma (atau implementasinya) untuk memproses sejumlah data n

LanjtRunning time-nya O(f(n)) O(f(n)) adalah sbgWorst case-nyaO(f(n)) batasan pd worst-case running time O(f(n)) batasan pada running time dari setiap input.

Q(f(n)) batasan pd worst-case running time Q(f(n)) batasan pd running time dari setiap input.Running time -nya W (f(n)) W(f(n)) sbg Best case-nya

Analisis Empiris ?