[問題] 102 專利商標 資料結構問題
Q1.請使用C或JAVA語言,寫一遞迴副程式,此副程式的輸入為一個未排序的且長度為n的整
數陣列A[0:n-1],副程式將在此整數陣列中,以遞迴的方式群找此整數陣列中的最大值
,並回傳此最大值。
Q2.請分析此副程式的時間複雜度以order的方式表示。
A1:
Int Max(int k , int a[i])
{
int max=a[k]
if (a[k]>a[i]) than return Max(k,k-1)
else return Max(k-1 , k-1)
}
不好意思,我的想法比較粗糙,我的想法是預設A[n]作為MAX,在每一回合一一往前(
陣列index較小的方向)比較,當max>a[i]時,下一回合就在跟a[i-1]比;同理,若
max<a[i-1],則max等於a[i-1],再繼續往前比較
請問版上前輩,我的想法有哪裡錯誤?另外程式方面我可以怎樣描述才比較完整?
A2:
因為我是循序去找陣列的最大值,所以最差會是O(N)嗎?order的方式表示是指甚麼意思?
還請版上前輩指教...謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.133.164
※ 文章網址: https://www.ptt.cc/bbs/Examination/M.1429716071.A.B61.html
→
04/23 09:57, , 1F
04/23 09:57, 1F
推
04/23 10:17, , 2F
04/23 10:17, 2F
推
04/23 10:23, , 3F
04/23 10:23, 3F
→
04/23 10:24, , 4F
04/23 10:24, 4F
→
04/23 10:26, , 5F
04/23 10:26, 5F
推
04/23 10:30, , 6F
04/23 10:30, 6F
→
04/23 10:31, , 7F
04/23 10:31, 7F
→
04/23 10:33, , 8F
04/23 10:33, 8F
→
04/23 10:34, , 9F
04/23 10:34, 9F
推
04/23 10:41, , 10F
04/23 10:41, 10F
→
04/23 10:45, , 11F
04/23 10:45, 11F
→
04/23 10:47, , 12F
04/23 10:47, 12F
討論串 (同標題文章)
以下文章回應了本文:
完整討論串 (本文為第 1 之 3 篇):