在分析各种算法的时间复杂度时，一般只讨论相应的数量级，用f（n）表示，请问其中n的含义是（）。

题目

在分析各种算法的时间复杂度时，一般只讨论相应的数量级，用f（n）表示，请问其中n的含义是（）。

相似考题

1.当问题的规模n趋向无穷大时,算法执行时间T(n)的数量级被称为算法的时间复杂度。()此题为判断题(对，错)。

2.A算法的时间复杂度为O(n^3),B算法的时间复杂度为O(2n),则说明()。A对于任何的数据量，A算法的时间开销都比B算法小B随着问题规模n的增大，A算法比B算法有效C随着问题规模n的增大，B算法比A算法有效D对于任何数据量，B算法的时间开销都比A算法小

3.算法的效率一般用什么来度量()A、时间复杂度B、空间复杂度C、执行的时间D、占用的空间

4.某算法的时间复杂度可用递归式[*],表示，若用[*]表示该算法的渐进时间复杂度的紧致界，则正确的是(62)。A．(nlg2n)B．(nlgn)C．(n2)D．(n3)

更多“在分析各种算法的时间复杂度时，一般只讨论相应的数量级，用f（n）”相关问题

  • 第1题：

    对于含n个顶点、e条边的无向连通图,利用Prim算法构造最小生成树的时间复杂度(),用Kruskal算法构造最小生成树的时间复杂度为()。

    A.O(n)

    B.O(n²)

    C.O(e)

    D.O(eloge)

    F.O(e²)


    参考答案：B,D

  • 第2题：

    若n表示问题的规模、O(f(n))表示算法的时间复杂度随n变化的增长趋势，则算法时间复杂度最小的是(59)。

    A．O(n2)

    B．O(n)

    C．O(logn)

    D．O(nlogn)


    正确答案：C
    解析：本题考查的是算法消耗的时间度量。一般情况下，一个算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n))，它表示随问题n的增大，算法执行时间的增长率和　f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。显然，在O(n2)、O(n)、　O(logn)和O(nlogn)中，复杂度最小的是O(logn)。

  • 第3题：

    算法复杂度包括时间复杂度和空间复杂度。对于时间复杂度，一般可以用平均性态和最坏情况复杂性来衡量：对于空间复杂度，一般指执行该算法所需要的【 】。


    正确答案：内存空间
    内存空间

  • 第4题：

    算法的空间复杂度记为：S（n）=O（f（n））。


    正确答案:正确

  • 第5题：

    排序的平均时间复杂度为O（n•logn）的算法是（），为O（n•n）的算法是（）


    正确答案:快速排序、二路归并排序、堆排序；直接插入排序、简单选择排序、起泡排序

  • 第6题：

    一个算法的时间复杂度为（3n2+2nlog2n+4n-7）/（5n），其数量级表示为（）。


    正确答案:O（n）

  • 第7题：

    算法的时间复杂度数量级包括（）。

    • A、线性阶O（n）
    • B、平方阶O（nn）
    • C、立方阶O（nnn）
    • D、对数阶O（log2n）

    正确答案:A,B,C,D

  • 第8题：

    一个算法的时间复杂度为（n+nlog2n+14n）/n，其数量级表示为（）。


    正确答案:O（n）

  • 第9题：

    在算法时间复杂度中，O（n3）表示平方阶


    正确答案:错误

  • 第10题：

    多选题
    算法的时间复杂度数量级包括（）。
    A

    线性阶O（n）

    B

    平方阶O（nn）

    C

    立方阶O（nnn）

    D

    对数阶O（log2n）


    正确答案： A,B
    解析： 暂无解析

  • 第11题：

    填空题
    一个算法的时间复杂度为（3n2+2nlog2n+4n-7）/（5n），其数量级表示为（）。

    正确答案： O（n）
    解析： 暂无解析

  • 第12题：

    填空题
    一个算法的时间复杂度为（n+nlog2n+14n）/n，其数量级表示为（）。

    正确答案： O（n）
    解析： 暂无解析

  • 第13题：

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


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

  • 第14题：

    计算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

  • 第15题：

    给定一个由n个数组成的序列，要求该序列的最长单调上升子序列，请设计对应的算法并分析其时间复杂度，如果时间复杂度劣于O（nlogn）的，将其优化为O（nlogn）时间复杂度的算法。


    正确答案: 假设当前已求出m[1..i-1]，当前保留的状态集合为S，下面计算m[i]。
    1、若存在状态k∈S，使得x[k]=x[i]，则状态m[i]必定不需保留，不必计算。因为，不妨设m[i]=m[j]+1，则x[j] 2、否则，m[i]=1+max{m[j]|x[j] 3、若2成立，则我们往S中增加了一个状态，为了保持S的性质，我们要对S进行维护，若存在状态k∈S，使得m[i]=m[k]，则我们有x[i]x[i]，j∈S}。于是状态k应从S中删去。
    从性质D和算法描述可以发现，S实际上是以x值为关键字（也是以m值为关键字）的有序集合。若使用平衡树实现有序集合S，则该算法的时间复杂度为O（n*logn）。（每个状态转移的状态数仅为O（1），而每次状态转移的时间变为O（logn））。

  • 第16题：

    什么是算法的渐近时间复杂度？如何分析一个算法的渐近时间复杂度？


    正确答案:算法的渐近时间复杂度是对算法的时间效率的度量。也就是对一个算法执行所需要的时间进行分析。一个算法执行所需要的具体时间与所使用的计算机系统的软、硬件性能及问题的规模等因素有关。为了比较算法本身的时间性能，应该采用能够反映算法本身的时间性能的度量。实际上，通常算法运行所需要的时间T是问题规模n的函数，可记为T（n）。所谓算法的渐近时间复杂度，是当问题规模充分大时，算法运行时间的增长趋势的度量。因为增长率的上限对算法的比较更具意义，所以经常分析的是算法运行时间的增长率的上限，这就是算法的时间复杂度的大O表示，也常简称为算法的时间复杂度。
    为了分析一个算法的时间复杂度，一般情况下需要考察算法中基本语句的执行次数，找出其与问题规模n的函数关系f（n），从而得到算法的渐近时间复杂度。所谓基本语句是执行次数与算法的执行次数成正比的语句，它是算法中的关键操作。算法的基本语句大多包含在循环和递归结构中，对于单循环结构，循环体中的简单语句就是基本语句，其执行次数的大O表示就是该算法段的渐近时间复杂度；对于并列的循环结构，要先分析各个循环结构的渐近时间复杂度，然后利用大O表示法的加法规则求出算法的时间复杂度；对于多层嵌套的循环结构，最内层循环中的简单语句就是算法的基本语句，要自外向内逐层分析各层循环的渐近时间复杂度，再利用大O表示法的乘法规则来求出算法的渐近时间复杂度。对于递归结构，则可以根据递归过程递推出基本语句的执行次数，进而得到它的大O表示。总之，只要分析求出算法中关键操作的执行次数与问题规模的函数关系，也就得到了该次数的大O表示，从而也就求出了算法的渐近时间复杂度。

  • 第17题：

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


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

  • 第18题：

    算法的时间复杂度记为：T（n）=O（f（n））。


    正确答案:正确

  • 第19题：

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


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

  • 第20题：

    顺序表各种算法，都有其时间复杂度，在n个结点的顺序表中，删除第i（1≤i≤n）个结点的时间复杂度是（）。

    • A、O（1）
    • B、O（n）
    • C、O（nlog2n）
    • D、O（log2n2）

    正确答案:B

  • 第21题：

    判断题
    算法的时间复杂度记为：T（n）=O（f（n））。
    A

    对

    B

    错


    正确答案： 对
    解析： 暂无解析

  • 第22题：

    填空题
    在分析各种算法的时间复杂度时，一般只讨论相应的数量级，用f（n）表示，请问其中n的含义是（）。

    正确答案： 处理问题的样本量
    解析： 暂无解析

  • 第23题：

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

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

相关内容