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

admin2014-04-17  46

问题 设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/llxi777K
0

最新回复(0)