申論 2下列的虛擬碼程式片段中，I 和S 均為遞迴函式（recursive function），I 和S 的參數A 是一個整數陣列；I 和S 的參數i 為不為負的整數，主要是做為陣列A 的索引（index）。假設陣列A 的元素個數為n，且其索引值為0 到n–1 之間的數值。虛擬碼swap x and y 的意思是將變數x 與變數y 的儲存值互換；亦即執行之後變數x的儲存值為執行前變數y 的儲存值，執行之後變數y 的儲存值為執行前變數x 的儲存值。令T(n)為呼叫函式I(A, n–1)的執行時間。T(n)會隨著陣列A 所儲存的數值不同而有所不同。S(A, i) {If i <= 0, then return;S(A, i – 1);I(A, i);Return; }I(A, i) {If i <= 0, then return;If A[i] < A[i – 1] {swap A[i] and A[i – 1] ;I(A, i – 1); }Return; }㈠請用O-notation 表示T(n)的上界（upper bound）；請用Ω-notation 表示T(n)的下界（lower bound）。（5 分）㈡請說明T(n)最大時，程式開始執行前陣列A 所儲存的數值有何特性？理由為何？（5 分）㈢請問函式S(A, n–1)的時間複雜度為何？請說明理由。（5 分）㈣請問執行函式S(A, n–1)後，陣列A 儲存的內容有何特性？請證明你的觀察。（10 分）101年公務人員高等考試三級考試試題 代號：36250類 科： 資訊處理科 目： 資料結構