9.0形为巩固-|||-5.若递归算法的递推式分别如下所示, T(1)=O(1), 求各算法对应的时间复杂度。(10分-|||-① T(n)=2T(n/2)+O(1)-|||-② T(n)=T(n-1)+n

根据递推式，可以使用主定理来求解时间复杂度：
① T(n) = 2T(n/2) + O(1)
根据主定理，a=2, b=2, d=0，因为logb(a) = log2(2) = 1 = d，所以时间复杂度为O(n^d * logn) = O(logn)。

② T(n) = T(n-1) + n
根据主定理，a=1, b=1, d=1，因为logb(a) = log1(1) = 0，所以时间复杂度为O(n^d * logn) = O(n)。