Q86.
當n>=2 時，T(n)=2T(n-1)+1；當n=1 時，T(n)=1 。請問T(n)之值是多少？
電腦軟體設計共同科目 · 乙級 · Q86
難易度分析
3 / 5
本題考查遞迴關係式的數學推導能力，需要將遞迴式展開並識別其成長趨勢。由於涉及指數級成長的分析，且需在多個時間複雜度選項中精確區分線性、多項式與指數差異，因此設定為中等難度。
正確答案：④
④ :2ⁿ-1 為正確解答。此遞迴關係式 T(n) = 2T(n-1) + 1 且 T(1) = 1，展開可得 T(n) = 2ⁿ - 1。驗證：T(1)=1=2¹-1、T(2)=2(1)+1=3=2²-1、T(3)=2(3)+1=7=2³-1，符合指數成長模式。
:2ⁿ-1 為正確解答。此遞迴關係式 T(n) = 2T(n-1) + 1 且 T(1) = 1，展開可得 T(n) = 2ⁿ - 1。驗證：T(1)=1=2¹-1、T(2)=2(1)+1=3=2²-1、T(3)=2(3)+1=7=2³-1，符合指數成長模式。錯誤選項解析
- ① log n:log n 是對數時間複雜度，常見於二分搜尋法或分治法每次將問題規模減半的情境。本遞迴關係式每次產生兩個子問題，並非對數成長。
- ② n:n 是線性時間複雜度，對應如 T(n) = T(n-1) + 1 的簡單遞迴。本題每次遞迴產生 2T(n-1) 兩個分支，成長速度遠快於線性。
- ③ n2-1:n²-1 是二次多項式成長，常見於氣泡排序或插入排序等雙層迴圈結構。本遞迴關係式為指數型成長，非多項式型。
Learning Tip
"此類遞迴關係式求解為資料結構常考題型。關鍵在於辨識遞迴類型：T(n) = aT(n-b) + f(n) 形式可用展開法（反覆代入）求解。本題為典型的指數遞迴，每次呼叫產生兩個子問題，解為 2ⁿ-1，與漢諾塔問題的移動次數相同。易混淆點在於將指數成長誤認為多項式成長，需特別注意遞迴樹的分支數與深度。"
學員答題分佈
①log n0%
②n0%
③n2-10%
④0%
0%此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！
