Prof. Drs. T. Basaruddin, Ph.D.

Video ini membahas perhitungan kompleksitas atau biaya algoritma substitusi mundur dalam konteks komputasi numerik. Kompleksitas algoritma dihitung berdasarkan jumlah operasi aritmetik yang terlibat, terutama perkalian yang merupakan operasi paling mahal. Cost algoritma substitusi mundur proporsional dengan N kuadrat per 2 flops, di mana N adalah ukuran matriks N kali N. Meskipun biayanya lumayan besar, namun dengan kecepatan mesin komputer generasi baru yang mencapai gigaflops per detik, eksekusi algoritma ini dapat dilakukan dengan efisien tergantung pada nilai N.

Nah, sebelum kita implementasikan ini dalam Octave, sekarang coba kita hitung kompleksitas atau kompleksitas.

Kadang-kadang ini kita sebut sebagai cost atau biaya untuk menghitung ini.

Saya akan introduce bahwa dalam komputasi numerik,

biasanya kita akan menghitung cost atau kompleksitas dari suatu algoritma

berdasarkan jumlah operasi aritmetik yang terlibat.

Dan ini bisa kita tidak harus sampai sangat detail,

tapi yang biasanya kita akan hitung itu adalah yang paling mahal,

dimana tidak perlu kita hitung perkalian dan penyumbelahan sekaligus.

Jadi di sini ada pembagian, sebetulnya ada perkalian, cukup diwakili dengan satu.

Nah, perhatikan bahwa biaya termahalnya kan ada di sini,

yaitu mengalihkan, ini kan inner product,

ini panjang dari faktor ini adalah dari I plus 1 sampai N,

panjang dari faktor saya adalah N minus I,

kemudian dari XI plus 1 sampai N, itu juga N minus I.

Berarti perkalian faktor dengan baris ini,

tapi ini harus terjadi bukan hanya untuk sebuah I,

tapi harus berjalan dari I sama dengan N,

sampai saya mulai dari N minus 1 sampai dengan 1.

Jadi N minus I, Nnya dari N minus 1 sampai dengan 1.

Nah, ini sama saja kalau saya tulis ulang dengan sigma,

coba perhatikan isinya pada saat I sama dengan N minus 1,

jadi 1 tambah 2 tambah 3 sampai dengan N minus 1.

sigma I dimana I nya dari 1 sampai N minus 1,

dan kita tahu ini adalah merupakan deret aritematika,

yang kalau dijumlakan akan sama dengan N,

kalikan dengan N minus 1 dibagi dengan 2.

Nah, kita dapat katakan bahwa untuk mengeksekusi algoritma substitusi mundur ini,

kapabila matriks saya berukuran N kali N,

maka costnya kita katakan sebagai N kuadrat per 2,

Yang paling mahal, leading term atau suku yang paling mahalnya itu diwakili oleh N kuadrat per 2.

Kalau Nnya besar gitu katakanlah Nnya 1 juta berarti 10 pangkat 6,

Nah, satuannya biasanya kita katakan sebagai flops,

Jadi, ada sejumlah N kuadrat per 2 flops untuk menyelesaikan algoritma ini,

Nah, itu saja apabila kita bandingkan seberapa cepat ini eksekusinya

akan tergantung pada kecepatan mesin komputer kita.

Mesin-mesin generasi baru itu sudah sangat cepat,

dengan kecepatan bisa sampai gigaflops per detik.

Jadi, kalau dalam 1 detik dia bisa menghitung giga itu kan 10 pangkat 9,

Jadi, kalau 10 pangkat 9 operasi aritmatik dalam 1 detik,

maka O N kuadrat tidak akan terlalu lama diselesaikan.

Jadi, kalau N saya 10 pangkat 9 ya akan sangat lama mengeksekusinya.

Ini yang dapat kita jelaskan sebagai summary untuk sistem persamaan segitiga.

Kita sudah bisa menyelesaikan apakah bentuknya segitiga bawah atau segitiga atas,

dan kita juga sudah tahu bahwa biaya untuk eksekusinya

itu proportional dengan N kuadrat per 2 flops.

Dan cost untuk segitiga bawah akan sama saja dengan segitiga atas,

persis sama biayanya yaitu N kuadrat per 2.