某算法的时间复杂度可用递归式,表示，若用表示该算法的渐进时间复杂度的紧致界，则正确的是(62)。

admin2021-01-13 22

问题某算法的时间复杂度可用递归式

,表示，若用表示该算法的渐进时间复杂度的紧致界，则正确的是(62)。

选项 A、

(nlg²n)
B、

(nlgn)
C、

(n²)
D、

(n³)

答案A

解析本题利用递归树方法求解。得到的递归树如下图所示：

由于C属于O(nlg²n)且C属于Ω(nlg²n)，所以总的时间复杂度为A。

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

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

【说明】假定用一个整型数组表示一个长整数，数组的每个元素存储长整数的一位数字，则实际的长整数m表示为：m=a[k]×10k-2+a[k一1]×10k-3+…+a[3]×10+a[2]其中a[1]保存该长整数的位数，a[0]保存该长整数的符号：0表示正数、
阅读以下说明和C++代码，将应填入(n)处的字句写在答题纸对应栏内。【说明】现要编写一个画矩形的程序，目前有两个画图程序：DP1和DP2，DP1用函数draw_a_line(x1，y1，x2，y2)画一条直线，DP2则用drawline(x1，x2，y
阅读下列说明和图，回答问题1到问题3，将解答填入答题纸的对应栏内。【说明】目前大多数操作系统都采用虚拟存储技术，这样可在较小的可用内存中执行较大的用户程序，可在内存中容纳更多程序并发执行。引入虚拟存储技术，其基本思想是利用大容量的外存来扩充内存，产生一
阅读下列说明和数据流图，回答问题l至问题3，将解答填入答题纸的对应栏内。【说明】图书管理系统旨在用计算机对图书进行管理，包括图书的购入、借阅、归还以及注销。管理人员可以查询某位读者、某种图书的借阅情况，还可以对当前图书借阅情况进行一些统计，给出统计表格
阅读以下说明和C++代码，将应填入(n)处的字句写在答题纸对应栏内。【说明】现有一个显示系统，要显示的图形有线Line、矩形Square，抽象出一个Shape类(接口)，有方法显示display()。需要新增图形Circle，又已知有类XXCircle实
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】设有m台完全相同的机器运行n个独立的任务，运行任务i所需要的时间为ti，要求确定一个调度方案，使的完成所有任务所需要的时间最短。假设任务已经按照其运行时间从大到小排序，算法基
当在软件工程的环境中考虑风险时，主要基于Charette提出的3个概念。以下选项中不属于这3个概念的是(1)。项目风险关系项目计划的成败，(2)关系着软件的生存能力。在进行软件工程风险分析时，项目管理人员要进行4种风险评估活动，这4种活动分别是(3)以及确
下面关于校验方法的叙述，(5)是正确的。
从下列叙述中选出5条正确的叙述，并把编号按从小到大次序排列，它们是(30)。　　　　①解释程序是接受源程序，将其转换成中间代码，然后对其解释执行，它并不产生机器代码　　　　②编译程序是把高级语言书写的程序，翻成中间代码，然后逐条执行，产生机器代码　　　
程序设计语言包括(41)等几个方面，它的基本成分包括(42)。Chomsky(乔姆斯基)提出了形式语言的分层理论，他定义了四类文法：短语结构文法、上下文有关文法、上下文无关文法和正则文法。一个文法可以用一个四元组G=(∑，V,S，P)表示，其中，∑是终结符

随机试题

IntheMiddleAges,students______.Accordingtothepassage,modernindustrymusthavedeveloped______.
患儿，7岁。吃了不干净黄瓜后，高热5小时，呕吐3次，惊厥2次，于7月份入院。体温40．4℃，面色苍白，四肢厥冷，脉搏细速，脑膜刺激征(－)，今天未排大便，6小时无尿。目前现存的护理诊断不包括
患者，女，52岁。颈前结喉右侧肿物3cm×3cm×2cm，质地较硬，表面不光，不能随吞咽而上下移动，同时伴有局部疼痛，音哑，临床考虑为石瘿。行同位素131I扫描，其结果多是()
系统性红斑狼疮的病因与下列哪几项有关?()
诺斯等学者认为：金融创新就是()。
普通高中演奏模块中培养学生演奏技能的正确方法是()。
读下图，回答问题。乙河流的水文特征是()。
价格需求弹性：指需求对价格变动的反应程度或敏感程度，其大小以系数Ep＝需求变动(%)÷价格变动(%)的绝对值来表示。根据上述定义，下面哪一种说法是正确的?()
高校专业的设置应该是高校、政府、市场以及社会等多种力量多重考量的结果，过于强调某一方面必然会导致失衡。要实现相对合理和均衡，就要在制度上提供平台，比如确保大学在设置专业时经过教授委员会或学术委员会等专门机构的集体论证。教育主管部门也应推动并尊重现代大学治理
Mostpeopleareright-handedandchildrenusuallyhavethesamehandednessastheirparents.Thissuggeststhatgenesareatwor

最新回复(0)

某算法的时间复杂度可用递归式,表示，若用表示该算法的渐进时间复杂度的紧致界，则正确的是(62)。

软件设计师上午基础知识考试

软考中级

【说明】假定用一个整型数组表示一个长整数，数组的每个元素存储长整数的一位数字，则实际的长整数m表示为：m=a[k]×10k-2+a[k一1]×10k-3+…+a[3]×10+a[2]其中a[1]保存该长整数的位数，a[0]保存该长整数的符号：0表示正数、

阅读以下说明和C++代码，将应填入(n)处的字句写在答题纸对应栏内。【说明】现要编写一个画矩形的程序，目前有两个画图程序：DP1和DP2，DP1用函数draw_a_line(x1，y1，x2，y2)画一条直线，DP2则用drawline(x1，x2，y

阅读以下说明和C++代码，将应填入(n)处的字句写在答题纸对应栏内。【说明】现有一个显示系统，要显示的图形有线Line、矩形Square，抽象出一个Shape类(接口)，有方法显示display()。需要新增图形Circle，又已知有类XXCircle实

下面关于校验方法的叙述，(5)是正确的。

IntheMiddleAges,students______.Accordingtothepassage,modernindustrymusthavedeveloped______.

患儿，7岁。吃了不干净黄瓜后，高热5小时，呕吐3次，惊厥2次，于7月份入院。体温40．4℃，面色苍白，四肢厥冷，脉搏细速，脑膜刺激征(－)，今天未排大便，6小时无尿。目前现存的护理诊断不包括

患者，女，52岁。颈前结喉右侧肿物3cm×3cm×2cm，质地较硬，表面不光，不能随吞咽而上下移动，同时伴有局部疼痛，音哑，临床考虑为石瘿。行同位素131I扫描，其结果多是()

系统性红斑狼疮的病因与下列哪几项有关?()

诺斯等学者认为：金融创新就是()。

普通高中演奏模块中培养学生演奏技能的正确方法是()。

读下图，回答问题。乙河流的水文特征是()。

价格需求弹性：指需求对价格变动的反应程度或敏感程度，其大小以系数Ep＝需求变动(%)÷价格变动(%)的绝对值来表示。根据上述定义，下面哪一种说法是正确的?()

Mostpeopleareright-handedandchildrenusuallyhavethesamehandednessastheirparents.Thissuggeststhatgenesareatwor

IntheMiddleAges,students.Accordingtothepassage,modernindustrymusthavedeveloped.