设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。order(int j，int m){ int i，temp； if(j＜m) { for(i=j；i＜=n；i++) if(a[i]＜a[j]) { temp=a[i]； a[i]=a[j]; a[j]=temp； } j++； order(j，m)； ／／递归调用 }}
【正确答案】
C
【答案解析】解析：order()函数是一个递归排序过程，设T(n)是排序n个元素所需要的时间。在排序n个元素时，算法的计算时间主要花费在递归调用order()上。第一次调用时，处理的元素序列个数为n-1，也就是对余下的n-1个元素进行排序，所需要的计算时间应为T(n-1)。又因为在其中的循环中，需要n-1次比较，所以排序n个元素所需要的时间为 T(n)=T(n-1)+n-1 n＞1 这样得到如下方程： T(1)=0 T(n)=T(n-1)+n-1 n＞1 求解过程为 T(n)=[T(n-2)+(n-2)]+(n-1) =[T(n-3)+(n-3)]+(n-2)+(n-1) =[T(1)+1]+2+…+n-1 =0+1+2+…+n-1 =n(n-1)／2 =O(n
2
)