2. 考研
  3. 设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。 order(int j，int m) { int i，temp； if(j＜m) { for(i=j；i＜=n；i++) if(a[i]＜a[j])

设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。 order(int j，int m) { int i，temp； if(j＜m) { for(i=j；i＜=n；i++) if(a[i]＜a[j])

admin2017-11-20  27
问题 设n是描述问题规模的非负整数，下面程序片段的时间复杂度是(    )。
order(int j，int m)
{
  int i，temp；
  if(j＜m)
  {
    for(i=j；i＜=n；i++)
    if(a＜a[j])
    {
    temp=a；
    a=a[j];
    a[j]=temp；
    }
    j++；
    order(j，m)；    ／／递归调用
    }
}
选项 A、O(n)
B、O(nlog2n)
C、O(n2)
D、O(n3)
答案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(n2)
转载请注明原文地址:https://kaotiyun.com/show/jNRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)