問題詳情
二、下列的虛擬碼程式片段中，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 所儲存的數值不同而有所不同。
【題組】⑴請用 O-notation 表示 T( n)的上界（upper bound）；請用Ω-notation 表示 T( n)的下界（lower bound）。（5 分）
參考答案
答案：D
難度：簡單0.886637
統計：A(50),B(33),C(8),D(1181),E(0)