niusouti.com

若一个算法中的语句频度之和为T（n)＝3720n+4nlogn，则算法的时间复杂度为 。【答案中所有字符使用半角字符】

题目

若一个算法中的语句频度之和为T（n)＝3720n+4nlogn，则算法的时间复杂度为 。【答案中所有字符使用半角字符】

相似考题

1.若一个算法中的语句频度之和为T(n)=3720n＋4nlogn,则算法的时间复杂度为 O(n)。()此题为判断题(对，错)。

2.设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n表示，则该算法的时间复杂度为(59)。A．O(1gn)B．O(nlgn)C．O(n)D．O(n2)

3.假设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n，T(1)=1表示，则该算法的时间复杂度为()A.O(logn)B.O(n*logn)C.O(n)D.O(n^2)

4.若算法中语句的最大频度为T(n)=2006n＋6n㏒n＋29㏒2n,则其时间复杂度为()。A、O(㏒n)B、O(n)C、O(n㏒n)D、O(㏒2n)

更多“若一个算法中的语句频度之和为T（n)＝3720n+4nlogn，则算法的时间复杂度为 。【答案中所有字符使用半角字符】”相关问题

  • 第1题：

    某算法的时间代价递推关系为T(n)=2T(n/2)+n，T(1)=1，则该算法的时间复杂度为______。

    A．O(n)

    B．

    C．O(n2)

    D．O(1)


    正确答案：B
    解析：由时间代价严格推出时间复杂度比较复杂，对于这种题，可用特例验证，不过需要注意的是特例不能取太少，至少n取到5，这样规律基本就可以确定了。
      T(1)=1
      T(2)=2T(1)+2=4
      T(3)=2T(1)+3=5
      T(4)=2T(2)+4=12
      T(5)=2T(2)+5=13
      很容易排除D选项，其递增速率介于O(n)和O(nsup>2</sup>)之间，故选B。

  • 第2题：

    设任意n个整数存放于数组A(1:n)中,试编写算法,将所有正数排在所有负数前面(要求算法复杂度为0(n))。


    参考答案：本题属于排序问题，只是排出正负，不排出大小。可在数组首尾设两个指针i和j，i自小至大搜索到负数停止，j自大至小搜索到正数停止。然后i和j所指数据交换，继续以上过程，直到 i=j为止。
    　　[算法描述]
    　　void Arrange(int A[],int n)
    　　//n个整数存于数组A中，本算法将数组中所有正数排在所有负数的前面
    　　{int i=0,j=n-1,x; //用类C编写，数组下标从0开始
    　　while(i　　{while(i0) i++;
    　　while(i　　if(i　　}// while(i　　}//算法Arrange结束.
    　　[算法讨论]对数组中元素各比较一次，比较次数为n。最佳情况(已排好,正数在前,负数在后)不发生交换，最差情况(负数均在正数前面)发生n/2次交换。用类c编写，数组界偶是0..n-1。空间复杂度为O(1).

  • 第3题：

    某算法的语句执行频度为(3n2logn＋n3＋8),其时间复杂度是O(n3)()

    此题为判断题(对，错)。


    参考答案：正确

  • 第4题：

    A算法的时间复杂度为O(n^3),B算法的时间复杂度为O(2n),则说明()。

    A对于任何的数据量，A算法的时间开销都比B算法小

    B随着问题规模n的增大，A算法比B算法有效

    C随着问题规模n的增大，B算法比A算法有效

    D对于任何数据量，B算法的时间开销都比A算法小


    参考答案：B

  • 第5题：

    ● 设某算法的计算时间表示为递推关系式T(n)= T(n-1) + n (n>0) 及T(0)=1，则该算法的时间复杂度为 （65） 。


    正确答案：D

  • 第6题：

    设某算法的计算时间表示为递推关系式T(n)＝T(n-1)+n(n＞O)及T(0)＝1，则该算法的时间复杂度为(65)。

    A．O(lgn)

    B．O (nlgn)

    C．O(n)

    D．O(n2)


    正确答案：D
    解析：本题考查算法设计基础知识。根据题目中给出的递推关系：T(n)＝T(n-1)+n＝T(n-2)+n-1+n＝…＝T(0)+1+2+…+n-1+n＝1+n(n+1)/2

  • 第7题：

    设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n表示，则该算法的时间复杂度为(1)。

    A．O(lgn)

    B．O(nlgn)

    C．O(n)

    D．O(n2)


    正确答案：B
    解析：运用数学递推公式，可以推算出数量级O(nlgn)。

  • 第8题：

    某个算法的时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为 （ ） ，若问题的规模增加了16倍，则运行时间增加 （请作答此空） 倍。

    A.16
    B.64
    C.256
    D.1024

    答案：C
    解析：
    对于递归式，假设T(1)=1，则：
    T(n)=T(n-1)+n
    =T(n-2)+n-1+n
    =T(n-3)+n-2+n-1+n
    =1+2+…+n-1+n
    =n(n+1)/2
    可见，时间复杂度为O(n2)。若问题的规模增加了16倍，则运行时间增加了162=256倍。

  • 第9题：

    某个算法的时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为（62），若问题的规模增加了16倍，则运行时间增加（63）倍。

    A.16
    B.64
    C.256
    D.1024

    答案：C
    解析：
    对于递归式，假设T(1)=1，则：
    T(n)=T(n-1)+n
    =T(n-2)+n-1+n
    =T(n-3)+n-2+n-1+n
    =1+2+…+n-1+n
    =n(n+1)/2
    可见，时间复杂度为O(n2)。若问题的规模增加了16倍，则运行时间增加了162=256倍。

  • 第10题：

    设某算法的计算时间表示为递推关系式T（n）＝T（n-1）+n（n＞O）及T（0）＝1，则该算法的时间复杂度为（ ）。

    A.O（lgn）
    B.O（nlgn）
    C.O（n）
    D.O（n^2）

    答案：D
    解析：
    本题考查算法设计基础知识。根据题目中给出的递推关系：T（n）＝T（n-1）+n＝T（n-2）+n-1+n＝…＝T（0）+1+2+…+n-1+n＝1+n（n+1）/2

  • 第11题：

    n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为（）；若采用邻接表存储，该算法的时间复杂度为（）。


    正确答案:O(n2) O(n+e)

  • 第12题：

    某算法的语句执行频度为（3n+nlog2n+n2+8），其时间复杂度表示（）。

    • A、O（n）
    • B、O（nlog2n）
    • C、O（n2）
    • D、O（log2n）

    正确答案:C

  • 第13题：

    写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为A－Z这26个字母和0－9这10个数字)。


    参考答案：由于字母共26个，加上数字符号10个共36个，所以设一长36的整型数组，前10个分量存放数字字符出现的次数，余下存放字母出现的次数。从字符串中读出数字字符时，字符的ASCII代码值减去数字字符 ‘0’的ASCII代码值，得出其数值(0..9)，字母的ASCII代码值减去字符‘A’的ASCII代码值加上10，存入其数组的对应下标分量中。遇其它符号不作处理，直至输入字符串结束。
    　　[算法描述]
    　　void Count()
    　　//统计输入字符串中数字字符和字母字符的个数。
    　　{int i，num[36];
    　　char ch;
    　　for(i=0;i<36;i++)num[i]=0;// 初始化
    　　while((ch=getchar())!=‘#’) //‘#’表示输入字符串结束。
    　　if(‘0’<=ch<=‘9’){i=ch-48;num[i]++;｝ // 数字字符
    　　else　if(‘A’<=ch<=‘Z’){i=ch-65+10;num[i]++;｝// 字母字符
    　　for(i=0;i<10;i++) // 输出数字字符的个数
    　　cout<<“数字”< 　　for(i=10;i<36;i++)// 求出字母字符的个数
    　　cout<<“字母字符”< 　　｝

  • 第14题：

    某算法的语句执行频度为(n2log2n＋n3＋8),其时间复杂度表示()。

    A、O(n)

    B、O(n2log2n)

    C、O(n3)

    D、O(log2n)


    参考答案：C

  • 第15题：

    算法中语句执行的频度就是算法的时间复杂度。()

    此题为判断题(对，错)。


    答案：错误

  • 第16题：

    若一个算法的时间复杂度为(n2+2n-3)/(2n)，其数量级表示为______。


    正确答案：O(n)
    O(n) 解析：算法的时间复杂度表示是根据问题规模的函数f(n)来衡量的，其中问题规模函数的表达式(n2+2n-3)/(2n)中，问题规模增长或减少的比与n一致。

  • 第17题：

    计算N!的递归算法如下，求解该算法的时间复杂度时，只考虑相乘操作，则算法的计算时间T(n)的递推关系式为(55)；对应时间复杂度为(56)。

    int Factorial (int n)

    {//计算n!

    if(n＜=1)return 1;

    else return n * Factorial(n-1);

    }

    (62)

    A．T(n)=T(n-1)+1

    B．T(n)=T(n-1)

    C．T(n)=2T(n-1)+1

    D．T(n)=2T(n-1)-1


    正确答案：A

  • 第18题：

    设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为()。

    A.n2

    B.O(nlgn)

    C.O(n)

    D.O(n2)


    正确答案：D

  • 第19题：

    在某个算法时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为（ ），若问题的规模增加了16倍，则运行时间增加（ ）倍。

    A.Θ(n) B.Θ(nlgn) C.Θ(n2) D.Θ(n2lgn) A.16 B.64 C.256 D.1024


    正确答案：C,C

  • 第20题：

    某个算法的时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为 （请作答此空） ，若问题的规模增加了16倍，则运行时间增加 （ ） 倍。

    A.O(n)
    B.O(nlgn)
    C.O(n2)
    D.O(n2lgn)

    答案：C
    解析：
    对于递归式，假设T(1)=1，则：
    T(n)=T(n-1)+n
    =T(n-2)+n-1+n
    =T(n-3)+n-2+n-1+n
    =1+2+…+n-1+n
    =n(n+1)/2
    可见，时间复杂度为O(n2)。若问题的规模增加了16倍，则运行时间增加了162=256倍。

  • 第21题：

    已知算法A的运行时间函数为T（n）=8T（n/2）+n2，其中n表示问题的规模，则该算法的时间复杂度为（ ）

    A.θ（n）
    B.θ（nlgn）
    C.θ（n2）
    D.θ（n3）

    答案：D
    解析：
    本题需要用到特定形式的递归式分析法：
    在本题中，a=8,b=2，故符合（1）的情况。时间复杂度为：O（n3）。a=16,b=4

  • 第22题：

    某个算法的时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为（62），若问题的规模增加了16倍，则运行时间增加（63）倍。

    A.O(n)
    B.O(nlgn)
    C.O(n2)
    D.O(n2lgn)

    答案：C
    解析：
    对于递归式，假设T(1)=1，则：
    T(n)=T(n-1)+n
    =T(n-2)+n-1+n
    =T(n-3)+n-2+n-1+n
    =1+2+…+n-1+n
    =n(n+1)/2
    可见，时间复杂度为O(n2)。若问题的规模增加了16倍，则运行时间增加了162=256倍。

  • 第23题：

    设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。


    正确答案:Ο（1）；Ο（nlog2n）

  • 第24题：

    填空题
    设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。

    正确答案： Ο（1）,Ο（nlog2n）
    解析： 暂无解析

相关内容