Research Space for Linear Algebra & Discrete Mathematics
老師上課是說以上皆非第8行call array[a1...an]是固定的數 不會隨n改變所以是o(n^2)然後遞迴發生在9 10行也就是2Cn/4Cn=0(1) //initial+o(n) //array分類 mod 4+o(n^2) //沒有遞迴 單純呼叫Q+2Cn/4 //下面對P的遞迴
你好，我不太清楚你行數是指哪邊我想法是:line 2:O(n)line3~6:O(n)line7:Cn/2line8:Cn/2共:Cn=2Cn/2+O(n)ab錯c因為3/2O(n)和O(n)同leveld多一個O(1)似乎也不影響...有錯請指正，萬分感謝
OK, 我覺得選(c),(d)沒問題, 只要不要選了(c),(d)又選(e)就好
張貼留言
3 則留言:
老師上課是說以上皆非
第8行call array[a1...an]
是固定的數 不會隨n改變
所以是o(n^2)
然後遞迴發生在9 10行
也就是2Cn/4
Cn=
0(1) //initial
+o(n) //array分類 mod 4
+o(n^2) //沒有遞迴 單純呼叫Q
+2Cn/4 //下面對P的遞迴
你好，我不太清楚你行數是指哪邊
我想法是:
line 2:O(n)
line3~6:O(n)
line7:Cn/2
line8:Cn/2
共:Cn=2Cn/2+O(n)
ab錯
c因為3/2O(n)和O(n)同level
d多一個O(1)似乎也不影響...
有錯請指正，萬分感謝
OK, 我覺得選(c),(d)沒問題,
只要不要選了(c),(d)又選(e)就好
張貼留言