Algoritma Strassen untuk analisis kompleksitas multiplikasi matriks

Saya melihat di mana-mana bahwa persamaan rekursif untuk kompleksitas Strassen alg adalah:

$$T(n) = 7T(\tfrac{n}{2})+O(n^2).$$ Ini tidak begitu jelas bagi saya. Parameter$n$ seharusnya ukuran input, tetapi tampaknya ini adalah satu dimensi dari matriks sedangkan ukuran input sebenarnya $n^2$. Juga, setiap matriks input dibagi menjadi 4 sub matriks sehingga tampaknya persamaan rekursif seharusnya $$T(n) = 7T(\tfrac{n}{4}) + O(n).$$

Memang benar parameternya $n$biasanya menunjukkan ukuran input, tetapi ini tidak selalu terjadi. Untuk perkalian matriks kuadrat,$n$menunjukkan jumlah baris (atau kolom). Untuk grafik,$n$ sering menunjukkan jumlah simpul, dan $m$jumlah tepi. Untuk algoritma pada fungsi Boolean,$n$ menunjukkan jumlah input, meskipun tabel kebenaran itu sendiri memiliki ukuran $2^n$. Ada banyak contoh lainnya.

Ini kembali ke ukuran matriks. Misalkan matriks aslinya adalah$n\times n$. Karena itu kami akan mempertimbangkan$T(n)$ sebagai perhitungan dua matriks dengan ukuran $n\times n$. Ketika kita membagi matriks asli menjadi 4 bagian, ukuran masing-masing bagian adalah$\frac{n}{2}\times \frac{n}{2}$. Oleh karena itu, biaya perhitungan perkalian dua matriks dengan ukuran ini adalah$T(\frac{n}{2})$.

Kompleksitas waktu seringkali didasarkan pada ukuran input, tetapi itu bukan persyaratan mutlak. Dalam hal ini, untuk perkalian matriks nxn, tampaknya paling alami untuk menghitung jumlah operasi berdasarkan n, bukan pada ukuran masalah nxn.