根据渐进分析，表达式序列：n4 lgn 2n 1000n n2/3 ..

2020年下半年上午试卷综合知识

第 65 题


知识点	算法分析基础排序
章/节	计算机软件知识

根据渐进分析，表达式序列：n⁴, lgn, 2ⁿ, 1000n, n^2/3, n!从低到高排序为（）。

A. Ign,1000n, n^2/3, n⁴, n!, 2ⁿ

B. n^2/3,1000n, lgn, n⁴, n!, 2ⁿ

C. lgn,1000n, n^2/3, 2ⁿ, n⁴, n!

D. Ign, n^2/3, 1000n, n⁴, 2ⁿ, n!

相关试题算法设计与分析

第65题

2013年下半年

在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用(64)算法设计策略;若定义问题的解空间，以深度优先的方式搜索解空间，则采用(65)算法设计策略。

第35题

2017年下半年

某模块内涉及多个功能，这些功能必须以特定的次序执行，则该模块的内聚类型为（）内聚。

第62题

2019年上半年

已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)。矩阵相乘满足结合律，如三个矩阵A、B、C相乘的顺序可以是(A*B)*C也可以是A*(B*C)。不同的相乘顺序所需进行的乘法次数可能有很大的差别。因此确定n..

知识点讲解

· 算法分析基础

· 排序

算法分析基础

时间复杂性

算法的时间复杂度分析主要是分析算法的运行时间，即算法所执行的基本操作数。即使对相同的输入规模，数据分布不相同也决定了算法执行不同的路径，因此所需要的执行时间也不相同。根据不同的输入，将算法的时间复杂度分为3种情况。

（1）最佳情况。使算法执行时间最少的输入。一般情况下，不进行算法在最佳情况下的时间复杂度分析。应用最佳情况分析的一个例子是已经证明基于比较的排序算法的时间复杂度下限为Ω(nlgn)，那么就不需要白费力气去想方设法将该类算法改进为线性时间复杂度。

（2）最坏情况。使算法执行时间最多的输入。一般会进行算法在最坏时间复杂度的分析，因为最坏情况是在任何输入下运行时间的一个上限，它提供了一个保障，情况不会比这更糟糕。另外，对于某些算法来说，最坏情况还是相当频繁的。而且大致上看，平均情况通常与最坏情况的时间复杂度一样。

（3）平均情况。算法的平均运行时间。一般来说，这种情况很难分析。举个简单的例子，现要排序10个不同的整数，输入就有10!种不同的情况，平均情况的时间复杂度要考虑每一种输入及其该输入的概率。平均情况分析可以按以下3个步骤进行。

①将所有的输入按其执行时间分类。

②确定每类输入发生的概率。

③确定每类输入的执行时间。

下式给出了一般算法在平均情况下的复杂度分析，即

式中，p_i为第i类输入发生的概率；t_i为第i类输入的执行时间，输入分为m类。

渐进符号

渐进符号有以下几种。

（1）Ο记号。给出一个函数的渐进上界。

（2）Ω记号。给出一个函数的渐进下界。

（3）Θ记号。给出一个函数的渐进上界和下界，即渐进确界。

递归式

从算法的结构上看，算法可以分为非递归形式和递归形式。非递归算法的时间复杂度分析较简单，本小节主要讨论递归算法的时间复杂度分析方法。

（1）展开法。将递归式中等式右边的项根据递归式进行替换，称为展开。展开后的项被再次展开，如此下去，直至得到一个求和表达式及其结果。

（2）代换法。这一名称来源于当归纳假设用较小值时，用所猜测的值代替函数的解。用代换法解递归式时需要两个步骤：猜测解的形式；用数学归纳法找出使解真正有效的常数。

（3）递归树法。递归树法弥补了代换法猜测困难的缺点，它适于提供"好"的猜测，然后用代换法证明。在递归树中，每一个节点都代表递归函数调用集合中每一个子问题的代价。将树中每一层内的代价相加得到一个每层代价的集合，再将每层的代价相加得到递归式所有层次的总代价。当用递归式表示分治算法的时间复杂度时，递归树的方法尤其有用。

（4）主方法。也称为主定理，给出求解以下形式的递归式的快速方法，即

T(n)=aT(n/b)+f(n)

式中，a≥1和b>1是常数；f(n)是一个渐进的正函数。

排序

假设含n个记录的文件内容为｛R₁，R₂，…，R_n｝，其相应的关键字为｛k₁，k₂，…，k_n｝。经过排序确定一种排列｛R_j₁，R_j₂，…，R_jn｝，使得它们的关键字满足如下递增（或递减）关系：k_j₁≤k_j₂≤…≤k_jn（或k_j₁≥k_j₂≥…≥k_jn）。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5