平方矩陣和運行時間

Question

我可以證明矩陣A的2 * 2的平方是O（n^log5），表明它只需要5次乘法。直到現在我沒有問題，但在我想解釋2個原因之後，爲什麼我們無法概括爲其他情況下的平方（不同的n * n大小），我可以拿出一個如下：

第一個我能想到的原因是我乘以例如3 * 3矩陣與自己，並得出結論，至少它有6個乘法，所以它的運行時間至少是O（n^log6），其中n^epson大於O（n^log5），所以它比較慢，我們不能概括所有情況下的O（n^log5）。現在我需要另一個理由，但我不能想出任何想法如何解釋任何人都可以幫助的第二個理由（我只需要一個提示來提出一個想法）？

Answer 1

你不可能從例子中以大的符號來得到運行時間。 Big-O符號告訴我們一些關於算法的複雜性如何隨着參數的增加而變化的情況（在這種情況下矩陣的大小爲n），所以如果你真的想通過實驗來逼近它，你至少需要計算幾個測試大小的運行時間。

但我懷疑你可以找到最佳的方式來手動平方100x100矩陣......這實際上是一個難題。我們可以肯定的是，它不比矩陣 - 矩陣產品更復雜。對於那些我們有歐米茄（n^2）下限的人，我們必須至少查看一次矩陣的每一個條目。而且我們對於（理論）完美算法的上限約爲O（n^2.3729），因爲存在已知該算法的算法。 （見http://en.wikipedia.org/wiki/Matrix_multiplication#Algorithms_for_efficient_matrix_multiplication）

順便2.3729 < LOG6你建議是最低的 - 這並不矛盾的說法，那你可能需要6次乘法的3x3矩陣，因爲再次：O型符號只在乎漸近行爲的運行時間，因爲n變大 - 而不是個別n的任何特定運行時間。