Re: [理工] 時間複雜度
: 若有一個矩陣大小均為n，此矩陣內的元素相加的時間複雜度為何？
: 答案是O(n)
:
: 但我在思考..這個程式要怎麼寫..
: 有人有好的idea嗎..
:
: 推 b41424344:這題不就是問從A[0]一直加到A[n-1]嗎?這樣當然是O(n)啊 08/29 17:26
: → b41424344:for(i=0;i<n;i++) { ans+=A[i]; } <-題目是要問這個嗎? 08/29 17:28
看到有人繼續回應 就仔細想想 應該是O(n)才對
對不起大家 那天算熬夜(看時間)看到這篇文章隨便想一下就回文了= =XD
不過b41424344大大那個code是錯的喔 是"矩陣相加"不是算總加成...
一個矩陣大小為均n 我把它儲存到陣列裡面好了寫個虛擬碼參考看看
(先不管link list方法)
矩陣一般人都會儲存到二維陣列 因為row*column 很符合直覺性
但其實也可以儲存到一維陣列的
矩陣加法就是對應元素相加 這點我想大家應該沒有甚麼疑義
先用二維陣列寫法比較清楚
Matrix_add(int i,int j){ //i代表矩陣row;j代表矩陣column
int A[i][j]; //矩陣的元素
int ans[i][j]; //我們要矩陣相加的結果
int n; //矩陣的大小
n=(i-1)*(j-1); //大小就是row*column 但i=j=0是1列1行 故要-1
for(int x=0;x<=i;x++)
for(int y=0;y<=jy++)
ans[i][j]=A[i][j]+A[i][j]; //對應的元素相加
}
時間複雜度應該是O(i*j)也就是O(n) 因為要注意n=(i-1)*(j-1)這邊
所以也是可以用一維陣列來儲存 比較可以看得出來
只是缺點是找index不太方便就是了(就不知道是幾行幾列)
Matrix_add(int n){
int A*;
int ans*;
for(int i=0;i<n;i++)
ans[i]=A[i]+A[i];
}
時間複雜度為O(n)
正確說法是n*n大小的矩陣相加才是O(n^2)才對
以上我沒有用程式跑過 隨手想一下寫一下 大概是這樣吧QQ
希望有回答你問題 應該是O(n)沒錯 這白癡問題我竟然想錯Orz
大概是某題庫答案錯誤很多 所以不太相信答案XDD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 36.231.36.134
推
08/31 01:39, , 1F
08/31 01:39, 1F
→
08/31 09:50, , 2F
08/31 09:50, 2F
→
08/31 14:33, , 3F
08/31 14:33, 3F
討論串 (同標題文章)
