時間複雜度的問題 |
答題得分者是:syntax
|
tzuhsun
一般會員 發表:7 回覆:8 積分:3 註冊:2007-03-25 發送簡訊給我 |
for(i=0;i<=998;i )
{ k=i; for(j=i 1;j<=999;j ) { if(Unknown[j]>Unknown[k]) k=j; count ;------------>1 } temp=Unknown[i]; Unknown[i]=Unknown[k]; Unknown[k]=temp; count ;------------------>2 } 請問各位大大 如果要算複雜度 那我count要加在1還是2 對於時間複雜度 我還是不太會~"~ 編輯記錄
dllee 重新編輯於 2007-04-21 18:58:38, 註解 修改文章分類由 無 -> 問題, 提問時, 請記得選擇 [問題] 分類, 才能把分數給辛苦答題的會員, 謝謝您的配合‧‧
|
syntax
尊榮會員 發表:26 回覆:1139 積分:1258 註冊:2002-04-23 發送簡訊給我 |
答案是:看你高興
時間複雜度的記次,看你定義何者可忽略,何者必需記次 所以 if 是否必需記次? = (assign) 是否必需記次? - * / 是否必需記次 如果所有的都必需,那就是每做一個動作,就累加記次一次 不過,通常都只針對你的主要對象做記次 因為你沒有運算,只有 assign,所以 for(i=0;i<=998;i ) { k=i;count ; for(j=i 1;j<=999;j ) { if(Unknown[j]>Unknown[k]) k=j;count ; } temp=Unknown[i];count ; Unknown[i]=Unknown[k];count ; Unknown[k]=temp;count ; } 所以是 n*(n 1)/2 3n O(n) = n^2 如果只對 for 記次,那就是 n*(n 1)/2 O(n) = n^2 所以其實 3n 是可以忽略的,這就是為何,有時候有的東西不計入記次範圍,因為,不影響結果 |
tzuhsun
一般會員 發表:7 回覆:8 積分:3 註冊:2007-03-25 發送簡訊給我 |
本站聲明 |
1. 本論壇為無營利行為之開放平台,所有文章都是由網友自行張貼,如牽涉到法律糾紛一切與本站無關。 2. 假如網友發表之內容涉及侵權,而損及您的利益,請立即通知版主刪除。 3. 請勿批評中華民國元首及政府或批評各政黨,是藍是綠本站無權干涉,但這裡不是政治性論壇! |