Halo, pada video kali ini kita akan membahas tentang, kita lanjut materian dulu tentang algoritma perkalian matriks ya dalam hal ini. Algoritma yang kita bahas itu adalah yang namanya algoritma Strassen, bagaimana cara kerjanya, lalu berapa kompleksitas waktu. waktu algoritma strassen.
Ilustrasi running algoritmanya bisa kalian lihat di file Jupyter Notebook ini dimana bisa dibuka dengan menggunakan Google collab lalu catatan kuliahnya bisa dilihat di file ini semua ada di Google Drive nanti juga ada problem set yang kalian harus jawab beserta Gimana cara menjawabnya ada di bawah ya oke Kalau misalkan kita diberikan 2 matriks A dan B, dalam kasus ini sekarang matriksnya itu adalah matriks persegi, yaitu dua-duanya itu N kali N. Nah kita ingin menghitung C, ya tentu saja nanti outputnya adalah N kali N juga. hasil perkalian dari A dan B. Nah, ya, algoritma Strassen ini sendiri ya, digunakannya untuk perkalian matriks persegi seperti ini. Nah, ide besar dari algoritma Strassen itu apa sih?
Yang pertama, mungkin kita melihat dulu untuk mempermudah kasus di mana n-nya itu adalah n sama dengan 2 pangkat sesuatu. Jadi dia misalkan 2, ukurannya 2, 4, 8, 16, dan seterusnya. Tapi nanti cara kerjanya juga sama kalau kita punya matrix yang berukuran 3, 5, 6, 7, yang bukan 2 pangkatnya, sama.
Jadi untuk suatu bilangan asli k. Ide besar yang pertama yang digunakan oleh Strassen itu adalah, kalau diberikan dua matriks B yang ukuran N x N, kita bisa menuliskan A dan B ini dalam bentuk blok. Blok itu dalam artian gini. Jadi misalkan kalau saya punya A, ini ada blok pertama, blok kedua, blok ketiga, blok keempat, itu dibagi menjadi 4 blok. Ini juga sama, dibagi menjadi 4 blok.
Nah, di mana masing-masing blok ini itu berukuran setengah dari ukuran aslinya. Jadi, kalau misalkan ini adalah ukuran N, maka ini ukurannya N per 2 kali N per 2 semua ya. Masuk yang ini juga, yang matriks yang ini juga.
Jadi, semuanya ukurannya N per 2 kali N per 2. Nah, seperti itu. Nah. Dimana kalau kasusnya tadi adalah n-nya 2 pangkat k, maka tentu saja jadi ukurannya itu 2 pangkat k-1 x 2 pangkat k-1. Kalau kita ambil contoh, misalnya kalau saya punya matriks A yang ukurannya 4 x 4, jadi ini A-nya 4 x 4. Inilah blok A11, ini blok A12, ini blok A21, ini blok A22. Jadi seperti itu.
Nah, kemudian kita misalkan hasil perkaliannya C itu juga dituliskan dalam blok-blok begini ya. Misalkan ini blok pertama, ini blok kedua, blok ketiga, blok keempat. Sama, ukurannya juga nanti setengah dari ukuran yang pertama, matriks aslinya. Nah, Strasen menggunakan 7 rumus berikut plus 7 tambah 4 ya, 11 rumus berikut untuk mendapatkan hasil perkalian matriks A kali B. Jadi ini rumus yang pertama, lalu ini rumus yang kedua, rumus yang ketiga, rumus yang keempat, rumus yang kelima, rumus yang keenam, rumus yang ketujuh.
Nah kalau kita baca paper aslinya yang ditulis oleh Strassen, ini mungkin sekitar tahun, saya lupa, mungkin tahun 70-an atau 60-an. Itu Strassen juga menuliskan langsung persamaan ini, jadi tidak ada semacam dia dapatnya dari mana, mungkin banyak juga yang mengatakan bahwa tidak. Strasen tidak menjelaskan Dari mana dia dapat rumus ini Ya bisa jadi memang Dia tiba-tiba aja dapat Dari mimpi itu dari mana ya Jadi dituliskan M1, M2, M3, M4 Sampai M7 seperti ini Dimana ini adalah Penjumlahan dan perkalian Kalau kita lihat ya Ini ada penjumlahan perkalian dari matriks-matriks yang blok tadi. Jadi kan ini blok dari A, ini blok dari A juga, ini adalah blok dari B. Itu dikali dan dijumlahkan.
Lalu untuk mendapatkan C-nya, ini kan C. Ini kan C. Kalau untuk mendapatkan C-nya, jadi C11 itu kita dapatkan dengan M. menggunakan rumus ini.
Jadi menggunakan M1, M4, M5, dan M7. Lalu C12-nya kita dapatkan dengan ini. C21 yang ini, C22 yang ini. Nah kira-kira gitu dia. Jadi kalau di sini itu tidak ada lagi perkalian.
Jadi perkaliannya itu hanya ada di yang sebelah sini aja. Di tempat menghitung MM ini, di situ hanya perkaliannya. Kalau saat menghitung C-nya sudah tidak ada lagi perkaliannya. Ya. Ya kita ambil contoh, misalkan saya punya matriks A dan B seperti ini, maka yang pertama kita hitung dulu M1.
Nah di sini kan karena sudah ukurannya 2x2, setengahnya kan berarti 1x1. Maka kalau kita tandai ya, ini dah A11 yang ini, ini A12, ini A21, ini A22, lalu ini B11, B12. B21, B22.
Jadi kalau mau pakai rumusnya, misalkan kalau kita ingin menghitung M1, itu kan A11 tambah A12. E A22. Jadi di sini tinggal 1 tambah 2, karena ini A11, ini A12 ya.
A22 itu 1. Jadi 1, yang ini A22. Lalu dikali dengan B11, B11-nya 1, B22-nya 1. A21 ditambah ya. Jadi ini 2 kali 2. Jadi ini 4. Lalu M2 nya itu adalah A21 tambah A22. A21 yang ini.
A22 yang ini. Jadi 2 tambah 1. Lalu dikali dengan B11. B11 nya yang ini kali 1. Ini sama dengan 3. Lalu M3 itu A11.
Yang ini 1 kali. B12 min B22, B12 yang ini 0 dikurangi dengan B22, B22 itu 1. Jadi ini min 1. M4 A22 1 lalu kali dengan B21 yang ini 1 min B11, B11 itu 1. Jadi ini 0. Lalu M5. Itu A11 ditambah A12.
Jadi 1 ditambah 2. Lalu dikali dengan B22. B22-nya 1. Lalu ini 3. Lalu M6. A21-A11.
A21-nya 2. Dikurangi dengan A11-nya 1. Dikali dengan B11-nya 1. Terus B12 nya 0. Jadi disini 1 dikali 1 ya. Lalu yang terakhir M7. A12 min A22.
A12 nya 2. Dikurangi A22 nya 1. Dikali B21 nya 1. Tambah B22 nya 1 juga. Jadi ini 1 kali 2, 2 ya. Nah sekarang untuk menghitung M.
Menghitung C satu-satunya itu menggunakan rumus ini. M1 tambah M4, 4 ditambah M4, tambah 0, dikurangi M5. M5-nya 3, lalu M7-nya 2. Jadi sama dengan 1 tambah 2 ini 3 ya. Lalu C12 nya itu pakai rumus yang bawah. C12 M3 tambah M5.
Jadi di sini min 1 plus 3 ya. Jadi di sini 2. Lalu C21 nya pakai M2 tambah M4. M2 nya 3. M4 nya 0. Jadi ini 3. lalu C22 nya itu C22 nya itu M1 min M2 jadi ini 4 min 3 ditambah M3 tambah M6.
Plus M3 minus 1 ditambah M6 itu 1. Jadi ini dengan ini habis 4 nya jadi 1 ya. Nah jadi inilah C nya. C nya itu jadinya 3, 2, 3, 1. Ya kalau dicoba kalikan langsung ya.
1. Ditambah 2 itu 3. 1 kali 0 tambah 2 itu 2. 2 kali 1 tambah 1. 3. 2 kali 0 tambah 1. 1 ya. Jadi benar. Nah kemudian gimana kalau misalkan n tidak sama dengan 2 pangkat k. Nah itu caranya itu adalah matrix dibuat agar menjadi berukuran 2 pangkat k dengan menambahkan n 3 0 ya.
Jadi kita tambahkan n 3 0. Tapi pada prakteknya nanti kalau kalian lihat programmingnya itu tidak harus. 2 pangkat K ya. Pada implementasinya itu biasanya kita membuat berukuran genap ya.
Jadi berukuran genap. Genap kan tidak harus 2 pangkat. Jadi bisa jadi berukuran 6. Itu 6 kan tidak 2 pangkat.
Jadi bisa juga dengan menggunakan itu. Jadi pada praktiknya kalau programmingnya ini mungkin tidak selalu ya. Tidak selalu.
yang paling aman itu adalah menggunakan dia tuh membuat dia berukuran genap karena bisa dibagi dua gitu jadi kalau 6 nanti kan ada 3 ada 3 kali 3 gitu ya nah kayak gitu nah tapi agar seperti ini biasanya sih dibuat dua banget lebih mudah nah kemudian sudah kodenya kira-kira gini jadi kalau kalian perhatikan ya Yang pertama misalkan A, B, Matrix, pergantungan C, hasilnya N, ukurannya. Nah misalkan ada fungsi namanya partisi blok. Partisi blok ini artinya untuk mendapatkan partisi dari Matrix A dan B. Jadi untuk mendapatkan 4 komponen ini.
Itu misalkan fungsinya namanya partisi blok. Lalu gabung blok ini adalah menggabungkan. Yaitu contohnya untuk mendapatkan C ini kita menggabungkan blok yang 4 ini. Nah, jadi cara kerjanya itu misalkan kita buat fungsi yang namanya fungsi strassen, di mana inputnya itu adalah matriks yang akan dikalikan. Kalau ukuran matriksnya itu 1x1, yaudah langsung kalikan saja, akan cuma bilangan selesai.
Nah, selain itu, kalau misalkan dia tidak satu, ukurannya tidak 1x1, maka yang pertama kita dapatkan dulu 4 blok dari matriks A, lalu kita dapatkan 4 blok dari matriks B, Lalu untuk mendapatkan M1-nya, kita menggunakan rumus yang tadi. Nah, tapi di sini kita memanggil ulang fungsi Strassen. Loh, kenapa demikian?
Karena kita kan mengalihkan matriks juga. Kalau kita lihat ya, di M1 ini, ini kan 2 matriks ini juga kan kita kalikan. Nah, karena perkalian matriks, ya kita ulang lagi memanggil algoritma Strassen untuk mengalihkan 2 matriks ini.
Begitu juga yang ini, matriks yang ini dan yang ini. Ini juga kita panggil ulang algoritma strassen untuk mengalikan dan seterusnya. Setiap ada perkalian kita memanggil fungsi strassen lagi.
Jadi di sini kita mengalikan A11 ditambah A22 dikalikan dengan B11 ditambah B22. Begitu seterusnya untuk M2, M3 dan seterusnya ya. Nah setelah itu untuk mendapatkan C-nya kita menggunakan rumus yang 4, yang rumus yang terakhir. Lalu kita return hasilnya itu adalah gabungkan yang ini ya.
Kira-kira gitu dia. Jadi ini cara kerjanya itu seperti kalau misalnya kita menghitung matriks 4x4. Jadi nanti kalau kita menghitung misalkan n-nya itu sama dengan 4. Maka nanti kita akan ada memanggil lagi untuk yang ukuran n per 2. Yaitu 2 gitu. Jadi nanti memanggil lagi lukuman strassen untuk menghitung perkalian matriks 2x2. Jadi dia secara rekursif dipanggil gitu.
Jadi memanggil fungsi strassen secara rekursif. Artinya dia dipanggil dirinya sendiri. Ini kan posisi stressnya di luar sini.
Jadi dipanggil lagi di sini. Jadi mengulang algoritma yang memanggil diri sendiri. Nah, yang seperti ini nantinya akan berpengaruh kepada gimana caranya kita menghitung kompleksitasnya.
Oke, sebelum kita ke sana, kita lihat dulu gimana sih implementasinya ya. implementasi dari algoritma strassen jadi kalau kita lihat nah disini kalau kalian perhatikan ada kondisi disini dimana kalau dia itu tidak genap maka kita lakukan padding padding itu artinya kita menambahkan kalau di python itu ada numpy namanya numpy ini numpy.pad ini gunanya adalah kita mempadding atau menambahkan entry dimana kita menambahkannya jadi disini tuh inilah index yang kita ini adalah bilangan yang menunjukkan Bukan bahwa kalau di sini 0 artinya di depan kita tidak menambahkan apa-apa. Kalau di sini 1 berarti di belakang kita menambahkan 1 entry.
Apa entry yang ditambahkan? Di sini ada kata modelnya constant ya. Constant kalau tidak di set, constantnya itu defaultnya 0. Nah ini jadi sama.
Y-nya juga di setiap barisnya itu tidak di depannya. Jadi seperti. Oh nanti deh saya kasih lihat gimana cara kerjanya ya.
Ini padding ini. Nah itu setelah di padding. Lalu ini adalah 7 rumusnya.
Lalu ini adalah 4 rumus terakhir. Dan ini kalau kalian lihat disini ada memanggil lagi fungsi strassennya. Nah kira-kira gitu.
Nah kalau misalkan saya punya matrix ini. Hai ini ukurannya 245 kali lima ini ya lima kali lima kalau kita kalikan nanti proses per-per-per apa namanya perukuran tuh gini Jadi kalau kurang satu kali satu ini hasil perkaliannya Oh ya semestinya dua kali dua ya Jadi ini kalau dua kali dua kali dua ini hasilnya Lalu disini yang 3x3 ini hasilnya. Yang ada lagi karena ini kan 5 ya ukurannya. Jadi dia kayak potongannya itu ya 3x2 gitu ya.
3x3 dengan 2x2 gitu. Eh, jangan kasih. Jadi buat 6 Jadi seperti inilah Jadi ada nanti yang ukurannya 2x2 Lalu Ada yang ukurannya 4x Ini Hasil lahirnya itu adalah Yang ini ya Ini matrix hasil lahirnya Yaitu 5x5 Harusnya saya tidak bisa scroll ya kita coba masukkan matrix yang misalkan ukurannya ukurannya 2x2 misalkan ya, eh 4x4 misalkan, jadi misalkan ini lalu ini saya hapus yang normal ya yang normal 4x4 Lalu baris yang terakhir saya hapus. Yang ini sama.
Hai Nah kalau ini kita run nanti ada nih harusnya 12 kali dua ya tapi kena dua kali dua ini hasil pakai matris dua kali duanya lalu nanti ini ada beberapa blok dua kali dua ya ada banyak Nah lalu nanti ini hasil akhir kok jadi lima kali lima ya hai hai Hai punya dasar ada keliru kayaknya fungsinya taruh 1234 1234 kayaknya yang ini aja nih hasilnya nih Oh ya yang ini yang terakhir nih ya kita coba kalau dua kali dua misalkan kalau dua kali dua yang mana sih saya kan kalau dua kali dua kedua kali dua batinnya hapus Hai ini dihapus ini dihapus ini dihapus Hai kek Hai mungkin harusnya ada mod ukuran nah jadi disini ukuran Oh iya bener ini satu kali satu itu maksudnya ya yang ini tuh Hai ada 41 kali satu ya terus disediakan dikumpulkan jadi satu jadi ini gitu ya tuh maksudnya ayah benar dapat jadi sudah benar satu kali satu eh ini hasil yang satu kali satu yang pertama itu satu yang kedua yang ketiga dengan empat tidak batasnya ini ya kalau kita coba langsung kalikan yang ini ya ini kan saat baris pertama bersebut dua bersebut pertama kali kolom pertama kolom pertama dari Matrix ini tuh min 10 ya 110 kali min 10 itu kan min 1 dan seterusnya. Nah, padding itu kayak gimana sih? Jadi, contohnya kalau misalkan saya punya matriks yang begini.
Ini ukurannya, ya nanti. Nah, jadi kalau saya kasih 2 di sini, maka 2 di belakang ini ditambahkan gitu. Dan ini disesuaikan dibuat dia menjadi matriks persegi. Tambahkan 2 baris. Nah, kalau misalkan angka yang 0 ini saya ganti dengan 1 gitu ya.
Maka di sebelum baris pertama ini, sebelum entry pertama ini akan ada tambahan unsur 0 juga. Jadi kalau kalian lihat. Nah, jadi ada tambahan unsur 0. Dan jadi ada satu tambahan baris 0 di atasnya gitu.
Kayak kira gitu. Jadi dia depan sama belakangnya ada gitu. Tapi kalau saya isi 0 di sini maka tidak ada menambahkan depan.
Nah, kira-kira gitu. Nah, lalu kita melakukan analisis sekarang. Jadi kalau kita misalkan Tn ini adalah banyaknya operasi penjumlahan dan perkalian sekaligus yang dilakukan saat menghitung perkalian matriks berukuran n kali n.
Jadi di sini... Tidak kita menghitung pemberian nilai, tidak menghitung komparasi dan lain-lainnya. Jadi yang kita hitung hanya penjumlahan dan perkalian.
Seperti pada yang sebelumnya juga yang perkalian matriks yang menggunakan Winograd dan standar. Nah kalau kita kembali melihat rumus yang digunakan Strasen, 7 rumus itu. Di sini bisa kita lihat, ketika kita mengalihkan matriks yang berukuran n kali n, kalau pertama kita hitung dulu ada berapa perkalian misalkan. Ada 1, 2, 3, 4, 5, 6, 7. Ada 7 perkalian.
Tapi perkalian ini adalah bukan perkalian bilangan biasa ya, tapi ini perkalian matriks berukuran n per 2 kali n per 2. Jadi itulah yang pertama di sini, poin pertama di sini. Jadi dia ada 7 perkalian matriks, tapi ukurannya itu n per 2 kali n per 2. Itu datang dari yang ini. Lalu ada berapa penjumlahan?
Kalau penjumlahan, kalau kalian hitung ada 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Lalu hitung yang ini, 11, 12, 13. 14, 15, 16, 17, 18. Nah, jadi ada 18 penjumlahan. Tapi ini juga sama. Penjumlahannya itu adalah penjumlahan matriks berukuran n kali n kali n. In per 2 kali n per 2. Nah, sehingga ingat ketika kita mengalihkan matriks ini berukuran n per 2 kali n per 2. Itu kan sama dengan kita harus memanggil lagi algoritma Strassen kan. Jadi ini sama dengan.
Jadi Tn-nya kalau dijumlah bagian yang sebelah sini ini adalah bagian perkalian. Lalu bagian yang sebelah sini ini penjumlahan. Nah, karena tadi ada 7 perkalian, nah masing-masing perkalian ini pasti dieksekusi sebanyak berapa kompleksitas yang mengalihkan matriks berukuran n per 2 kali n per 2, sehingga jadinya di sini 7 kali t n per 2. Karena untuk mengeksekusi perkalian matriks berukuran n per 2 kali n per 2, dengan menggunakan strassen, kita menggunakan sebanyak Tn per 2 disini. Karena kan sama Tn per 2 kan banyaknya operasi penjumlahan dan perkalian yang dilakukan saat menghitung perkalian 2 matriks berukuran n per 2 kali n per 2. Nah sehingga disini rumusnya 7 kali Tn per 2, karena ada 7. Lalu ada 18 penjumlahan, kenapa dia n per 2 kuadrat? Karena kan saat kalian menjumlahkan matriks, contoh menjumlahkan matriks, A, B, C, D dengan E, F, G, H. Ini kan ada penjumlahan yang kita lakukan, itu ada sebanyak berapa entry-nya, kan?
Nah, kalau dalam hal ini, ini ada sebanyak 4 kali kita menjumlahkan. Nah, kalau dia ukurannya N per 2 kali N per 2, maka pasti ada sebanyak N per 2 kali N per 2 kali, atau sebanyak N per 2 sekuadrat. Nah, sehingga totalnya Tn itu memenuhi persamaan ini.
Penjumlahan. Jadi, matriks berukuran 2x2. Untuk mempermudah.
Nah, kalau n-nya sama dengan 1, ya namanya bilangan. Kan ini kalau 1x1 kan cuma 1 bilangan ya. Misalkan ini bilangan A.
Matriksnya ukuran 1x1. Bilangan B matriks 1x1 ya perkaliannya A x B langsung gitu ya. Jadi cuma ada satu operasi. Yang dalam hal ini perkalian bilangan. Nah sekarang kita mau tahu nih.
Tn ini sebenarnya sama dengan berapa. Kalau kita ingin tahu berarti kan kita harus menghilangkan suku T di sebelah sini ya. Jadi agar dia benar-benar Tn nya itu benar-benar fungsi dalam n. Tidak ada lagi suku.
Memanggil dirinya sendiri Nah, ini kan persama rekursif Seperti pada saat kita menghitung Kompleksitas dari algoritma Winograd Eh, Winograd ya bener Saya lupa Saya pernah sebelumnya lah Nah, untuk mempermudah dulu Kita coba misalkan ukurannya itu 2 pangkat K Jadi N-nya sama dengan 2 pangkat K Dimana K-nya bilangan asli Kalau kita menghitung T2 pangkat K menggunakan rumus yang tadi, itu kita dapat persamaan ini. Lalu kalau kita menggunakan T2 pangkat K-1 untuk kita hitung di sebelah sini nanti ya, kita masukkan ini ke sini nanti. Ya sama, kita menggunakan ini, menggunakan rumus yang tadi. Rumus yang ini maksud saya ya, rumus yang ini. Lalu begitu terus sampai dia T2.
Itu nanti akan berhenti 7 kali T1 tambah 18 kali 1 kuadrat Kenapa berhenti disini? Karena T1 nya sudah ketahuan nilainya Ini kan sama dengan 1 Yaudah tidak usah lagi T1 sama dengan Ya disini bisa tulis T1 sama dengan 1 Jadi sudah cukup gitu Nah kalau kita substitusi semua persamaan ini Kedalam persamaan awal yang ada disini Jadi kayak ini saya substitusi kesini Lalu yang T2 pangkat K-2 saya substitusi kesini Dan seterusnya gitu. Maka kita akan punya contoh ya. Jadi nilai yang ini. Ini adalah T2 pangkat K-1.
Lalu saya substitusi. Kita substitusi. Kita akan dapat ini.
Lalu sekarang nilai yang sebelah sini. Ini adalah T2 pangkat K-2. Dan seterusnya ya. Kalau kita ikuti ya.
Maka kita akan dapat pola seperti ini. Jadi kita akan dapat 7 pangkat 3, 2 pangkat kamin 3, terus ini ada semacam 7 kuadrat x 18, 7 x 18, terus 7 pangkat 0 x 18, terus dikalikan 2 pangkat. Atau secara umum, nanti kalau kita berhenti di 1, kita akan punya... 7 pangkat K kali T1, 7 pangkat K min 1 kali 18 kali 2 pangkat 0 kuadrat, 7 pangkat K min 2 kali 18, 2 pangkat 1 kuadrat, dan seterusnya sampai nanti terakhir ada 18 yang tidak ada angka 7-nya. Atau kalau dibuatkan rumus umumnya, jadi di sini 7 dan 2-nya itu jalan pangkatnya ya.
Jadi di sini 7 pangkat K-nya yang ini, karena ini sama dengan 1, jadi sisa 7 pangkat K yang sebelah sini. 18 nya bisa keluar karena semua ada 18. Lalu yang ini jalan dari i sama dengan 0. Contoh kalau i sama dengan 0 ini 2 pangkat 0 ini 7 pangkat k-1 yaitu suku yang sebelah sini. Kalau i nya sama dengan 1 itu jadi k-2 lalu 2 pangkat 1 itu suku yang sebelah sini. Dan seterusnya kalau k nya sama dengan k-1 misalkan. Maka kita akan dapat suku yang.
Sebelah sini ya. Karena jadi 7 pangkat 0, 2 pangkat K-1. Dan seterusnya.
Nah, kalau kalian perhatikan. Yang sebelah sini ini. Bisa kita ubah menjadi begini.
Keluarkan 7 pangkat K-1-nya. Yang ini ya. Lalu kita keluarkan. Lalu kita dapat. Yang ini.
Ini adalah jumlahan. jumlahan barisan geometri ya dengan suku awal sama dengan satu ini suka awalnya satu karena iso mereka nolakan 22 per 7 pangkat nolkan satu lalu rasionya rasionya bisa dilihat ini dua pertujuh dua pertujuh kan kurang dari satu nah sehingga kita dapatkanlah Ini bisa dipersikat dengan menggunakan ini. Ini adalah jumlahan barisan geometri, k-suku barisan geometri dengan rasio 2 per 7 dan suku awalnya 1. Kalau disimplifikasi kita akan dapat seperti ini. Lalu kita catat bahwa 2 log 7 itu 2,8073 sekian-sekian yang tidak berhenti ini. Atau kita ambil 2,807 aja.
Maka 7 ini bisa saya ganti dengan. Oh bentar. 7 nya bisa saya ganti dengan.
Ya ini sama dengan mengatakan bahwa. 7 itu sama dengan 2. Kira-kira gitu ya. 2 pangkat 2,807. Nah itu.
Jadi 7 nya semua. 7 yang ini. Saya ganti dengan. Dengan menggunakan ini.
Dengan menggunakan ini ya. Maka nanti TN-nya akan kita dapat 2 pangkat ini. Nah yang ini kan bisa ditukar pangkatnya ya.
Jadi K-nya yang ke dalam. Ini yang keluar. Jadi kita dapat 2 pangkat K.
Ingat 2 pangkat N kan sama dengan 2 pangkat K. Jadi ini kita dapat. N pangkat 2,807 kali 23 per 5 lalu yang ini pangkat N. Dan ini adalah big O, pangkat tertingginya adalah 2,807.
Kalau menggunakan limit kita akan dapat ini big O 2,807. Yang kalau kalian perhatikan, kalau ingat ya. Dulu Winograd, Winograd, Winograd terus.
secara perkalian standar itu tuh kompleksitasnya kompleksitasnya itu kan Big O n pangkat tiga kan ya kalau kita menggunakan ABCD nya sama semua m kali n kali k kali l nya itu m kali n m n dan k nya itu sama semua sama dengan n itu n pangkat tiga kalau kalian lihat di sini sedikit kurang dari tiga gitu nah sehingga untuk n yang besar itu harusnya algoritma strassen ini lebih efisien dibandingkan dengan dua algoritma sebelumnya jadi tapi ini dengan catatan untuk n yang besar karena ini sebenarnya kalau on banyak juga pengalinya disini jadi kalau kita coba lihat apa namanya hitung runningnya Oke, kalau kita coba hitung waktu runningnya, ini untuk matrix yang sama ya. Bentar, bukan yang ini. ya kalau kita punya matrixnya oh disini AB Kalau saya punya matrix 4x4, maka ini hasilnya dan waktu eksekusinya itu 1,54 ms. Ini adalah matrix yang dulu kita pakai. Coba kalau kita hitung kalau perkalian matrix yang dulu.
Ini matrix yang kemarin. Kalau kita coba. Oke, ini kalau kita coba matrixnya. Matrixnya sama dengan yang tadi ya.
lalu kita coba kalau perkalian dengan perkalian standar itu kan 0, nah ini kalau kalian lihat ini 1, sedangkan yang ini 0, itu seperti saya bilang kalau untuk n yang kecil itu masih lebih bagus yang ini tapi untuk n yang besar nanti karena dia itu 2 n pangkat 2,8 sekian jadi saja dia lebih efisien tapi untuk kasus yang kecil contoh kalau Winograd juga kalau Winograd kita pakai untuk menghitung Hai ini sama 0,9 masih jauh lebih banyak yang ini ya Nah tapi kalau untuk n yang besar itu dia lebih bagus Oke kira-kira itu aja Oh sampai ketemu di video selanjutnya