Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas teorema 2 Estimasi Ukuran Fungsi dalam Matematika Diskrit dengan judul "Teknik Perhitungan Lanjutan". Teorema tersebut menyatakan bahwa jika F1x adalah big O dari G1x dan F2x adalah big O dari G2x, maka F1 plus F2x adalah big O dari maksimum harga mutlak G1x dengan harga mutlak G2x. Konsep lain yang dibahas adalah master theorem yang digunakan untuk memperkirakan kompleksitas algoritma. Dengan menggunakan teorema ini, kita dapat menentukan kompleksitas algoritma seperti merge sort dan perkalian cepat. Sebagai contoh, kompleksitas merge sort dapat diestimasi sebagai big O dari N log N.

Sekarang kalau kita punya hasil yang tadi itu kita bisa tuliskan dalam suatu teorema

yaitu kalau F1x adalah big O dari G1x dan F2x adalah big O dari G2x

maka F1 plus F2x adalah big O dari maksimum harga mutlak G1x dengan harga mutlak G2x

jadi ini kesimpulan dari yang kita bahas sebelumnya

ada teorema lain yang kita sebut sebagai master theorem

di sini fungsinya sama Fnya naik dan memenuhi relasi recurrency adalah Fn sama dengan A dari Fn per B ditambah C kali n per D

jadi bedanya sama yang sebelumnya adalah yang suku yang terakhir

kalau yang sebelumnya kan cuma plus C kalau di sini plus C dikali n per D

nah ini sama Nnya harus sama dengan BK dengan K suatu bilangan bulat positif

A nya lebih besar sama dengan 1 dan B nya itu tadi harus lebih besar 1

C dan D adalah bilangan real yang positif dan untuk D itu tak negatif

maka nanti Fn itu akan bisa dicari nilai big O nya tergantung dari perbandingan A dengan B pangkat D

kalau A nya lebih kecil dari B pangkat D maka Fn adalah big O dari ND

sedangkan kalau A nya sama dengan B pangkat D maka Fn adalah big O N pangkat D dikali log N

kalau A nya lebih besar B pangkat D maka Fn adalah big O dari N pangkat log B dikali dengan A

jadi nilainya itu bergantung pada apakah A nya lebih kecil dari B pangkat D atau sama dengan atau lebih besar

ini bisa kita pakai misalnya untuk melihat kompleksitas dari merge sort yang sebelumnya sudah kita bahas

dan kita sudah dapatkan sebelumnya bahwa Mn proses untuk mengurutkan N elemen tadi itu sama dengan 2 dikali M dari N per 2 plus N

kemudian dari teorema master kita bisa lihat dia bandingkan AB nya tadi

kita akan peroleh bahwa si Mn tadi adalah big O dari N log N

kita lihat di sini kenapa beberapa contoh terakhir itu fungsinya N per 2

karena itu modelnya kan kalau masih ingat kita bagi 2

makanya fungsinya dihitung dari N per 2 di sebelah kiri kalau dilihat dari diagramnya dan juga N per 2 di sebelah kanan

sekarang kalau kita melihat algoritma untuk yang perkalian cepat

Fn nya itu sama dengan 3 kali F dari N per 2 ditambah Cn

di sini N nya genap, Fn adalah banyaknya operasi bit untuk mengalihkan 2 bilangan bulat N bit

algoritmanya kita pakai Fast Multiplication

disini kita akan dapatkan dari teoremanya bahwa Fn nya akan sama dengan big O

atau Fn adalah big O dari N pangkat log 3

ini seringkali memang ditulis Fn sama dengan big O dari N pangkat log 3

tapi sama dengannya disini bukan sama dengan dalam arti matematis yang biasa

tapi itu bisa dinyatakan atau bisa diestimasi dengan fungsi N pangkat log 3

maka kalau kita mau pakai bilangan yang bulat itu adalah big O dari N pangkat log 3