设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。order (int j，int m) }int i，ternp；if(j＜m){if(a[i]＜a[j]){temp=a [i]；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
)