Adakah yang bisa memberi tahu saya Kompleksitas Penjumlahan & Pengurangan untuk algoritma Perkalian Matriks Bagi & Taklukkan?

Adakah yang bisa memberi tahu saya Kompleksitas Penjumlahan & Pengurangan untuk algoritma Perkalian Matriks Bagi & Taklukkan?

Saya tahu bahwa kompleksitas operasi penjumlahan dan pengurangan perkalian matriks Klasik adalah (n^3-n^2) sedangkan operasi Strassen adalah 6n^2.81 – 6n^2... tetapi sepertinya saya tidak dapat menemukan Divide & Conquer dimana saja. Bayangkan saja jika ada yang tahu, kalian pasti tahu. Terima kasih


algorithm matrix matrix-multiplication complexity-theory
person user1189352    schedule 20.02.2012    source sumber
comment
Pendekatan standar bagi dan taklukkan masih bersifat kubik -- relasi perulangannya adalah T(n) = 8T(n/2) + O(n^2), yang merupakan kubik berdasarkan teorema utama. Saya tidak tahu konstanta pastinya, maaf.   -  person Stuart Golodetz    schedule 20.02.2012
comment
kemungkinan duplikat Apakah Perkalian Matriks Divide & Conquer berfungsi jumlah penjumlahan/pengurangan yang sama dengan perkalian Matriks Klasik?   -  person ninjagecko    schedule 23.02.2012

Jawaban (1)


arrow_upward
1
arrow_downward

Ini mungkin bisa membantu. Lihat bagian pendahuluan sebelum Metode Strassen.

person Tejas Patil    schedule 20.02.2012