→ metalalive:第一題是 O(n),它會check n/2 次 if statment 11/08 17:53
simple function(x)
{
for(i=1,2,...,n/2)
if(i^2 = x)
cout<< i
}
以上程式執行複雜度為polynomial time? prove or disprove it
----------------------
一種著名的矩陣乘法計算演算法為 Sreassen's Algorithm
其原理是將2x2矩陣分割成使用 7次乘法 和18 次加法運算
運算複雜度可用遞回公式:
T(n) = 7 T(n/2) + O(n^2) 表示
若今天我們設計一個類似演算法 將矩陣分3次乘法以及10次加法計算n*n矩陣
其計算複雜度為??
----------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.21.191