设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 21

问题设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(nlog₂n)
C、O(n²)
D、O(n³)

答案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²)

转载请注明原文地址:https://jikaoti.com/ti/WEfjFFFM

本试题收录于：计算机408题库学硕统考专业分类

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

最早测量子午线的长度，并主持修订了当时最先进历法《大衍历》的是僧人()。

蒙古军西征之后，罗斯处于()的控制之下。

夏王朝建立后，将其领土划分为九州，派九牧进行治理，在九州范围内根据土地的肥沃程度缴纳贡赋，称为()。

开皇五年，文帝规定每年正月五日县令出查，令百姓五党三党为一团，根据标准定户等上下，从轻制定税额，并将各户应纳税额写成定簿，是为()。

在1875年宪法中关于法国立法权的叙述，不正确的是()。

关于美国内战，不正确的说法是()。

19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

在周初分封中，分封同姓诸侯国、异姓诸侯国，也分封圣王之后，下面属于圣王之后的封国为()。

论述欧洲一体化的进程及影响。

衡量全球化的指标有哪些?

细胞毒试验可用于

大脑皮质是人体活动的最高中枢，在不同部位，有完成某些反射活动的相对集中区，其中躯体感觉区位于

结核瘤的一般概述哪项是错误的

关于对涉嫌垄断行为的调查要求，叙述错误的是()。

某工程项目施工过程中，施工单位根据建设单位提供的地下管线资料进行基坑挖掘作业，不慎将一根未标识的电缆挖断造成停电事故，则对该起事故应承担责任的是()。

下列关于税收抵免限额的描述中正确的是()。