申論題

一、考慮下列程式片段： S1: procedure P(L) /* L 唯一串數字*/ S2: 若 L 的長度為 2, 則 return 此二數字之和 S3: L1 = L 的前半部分 /* if L=1234，L1=12 */ S4: L2 = 將 L 分成四部分，為第 2 及第 3 部分之組合 /* if L=1234，L2=23 */ S5: L3 = L 的後半部分 /* if L=1234，L3=34 */ S6: return(P(L1)+P(L2)+P(L3))

⑵若 S2 的計算時間與 L 的長度無關，而 S3 到 S5 的計算時間則與 L 的長度有關。若 L 的長度為 N，則 P(L)的計算時間複雜度為何？（10 分）