[問題] 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

→ malowda: 你的參數有寫錯嗎？一個是a[i]一個是常數 04/23 09:57

推 lei70200: 感覺少了些參數，而且陣列應該是丟a[]不是丟a[i]吧 04/23 10:17

推 lei70200: 你的想法是比較完後遞迴，應該還要再加個目前陣列大小的 04/23 10:23

→ lei70200: 參數，可是這樣做起來的感覺就跟比較完後For loop一樣.. 04/23 10:24

→ lei70200: 不太像遞迴的遞迴... 04/23 10:26

推 lei70200: 第二個應該是請你用排序好的串列去解釋他的時間複雜度 04/23 10:30

→ lei70200: 複雜度是O(N)沒錯，因為每一項都會比較過 04/23 10:31

→ lei70200: 喔~有點錯誤~是根據你的程式寫怎樣複雜度才會怎樣，不完 04/23 10:33

→ lei70200: 全是O(n)，其他有待高手補充@@ 04/23 10:34

推 lannany: 我覺得邏輯很像不正確 04/23 10:41

→ malowda: 終止條件也寫錯這個答案是無窮迴圈 04/23 10:45

→ malowda: 邏輯完全錯誤，order就是循序 04/23 10:47