102 專利商標 資料結構問題 - 考試

※ 引述《malowda (malowda)》之銘言：
: ※ 引述《eevvaag (Len)》之銘言：
: : 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)
: : }

原po的程式應改成:

Int Max(int k, int i, int [] a)
{
if (i==0) return (a[k]>a[0])?a[k]:a[0];

if (a[k]>a[i]) return Max(k, i-1, a);
else return Max(i, i-1, a);
}

另外由於是out of order，
每個index中value都必須被檢視，
Best cas的Time compliexity是O(n)

初始呼叫 Max(n, n-1, a) //

: int Max(int n , int a[])
: {
: if(n==0)return a[0];
: else
: {
: int max=Max(n-1,a);
: return (max>a[n])?max:a[n];
: }
: }
: : 不好意思,我的想法比較粗糙，我的想法是預設A[n]作為MAX,在每一回合一一往前(
: : 陣列index較小的方向)比較，當max>a[i]時，下一回合就在跟a[i-1]比；同理，若
: : max<a[i-1]，則max等於a[i-1]，再繼續往前比較
: : 請問版上前輩，我的想法有哪裡錯誤?另外程式方面我可以怎樣描述才比較完整?
: : A2:
: : 因為我是循序去找陣列的最大值，所以最差會是O(N)嗎?order的方式表示是指甚麼意思?
: : 還請版上前輩指教...謝謝

--
為何鄉民最近總是鬥志高昂戰鬥力旺盛呢?
該給個合理的解釋

--