有如下递归函数fact(n)，分析其时间复杂度。 fact(int n) { if(n

admin2014-12-25 98

问题有如下递归函数fact(n)，分析其时间复杂度。
fact(int n)
{
if(n<=1)return(1)； ①
elsereturn(n*fact(n一1))； ②
}

选项

答案设fact(n)的运行时间函数是T(n)。该函数中语句①的运行时间是O(1)，语句②的运行时间是T(n一1)+O(1)，其中O(1)为运算的时间。因此 [*] 则：T(n)=O(1)+T(n一1) =2*O(1)+T(n一2) … =(n一1)*O(1)+T(1) =n*O(1) =O(n) 即fact(n)的时间复杂度为O(n)。

解析

转载请注明原文地址:https://www.kaotiyun.com/show/xeVx777K

本试题收录于：数据结构导论题库理工类分类

数据结构导论

理工类

相关试题推荐

系统如图所示，G(s)=，其中a=0．4，b=0．5，试求：(1)系统的开环零点及开环极点；(2)系统的闭环零点及闭环极点；(3)系统的阻尼比ζ和无阻尼自然频率ωn。
某单位分配到一个地址块138．24．13．64／26，现在需要进一步划分为8个一样大的子网，则每个子网的网络前缀为多少位?每个子网有多少个IP地址?每个子网的地址块是什么?
IP地址中的网络号所占位数越多，则一个网络内可以容纳的主机数_______。
通信双方可以同时发送和接收信息，这种通信方式称为【】
______是指网络中建立通信的两台计算机之间由一条物理信道相连接，数据分组由源点计算机直接或者经过转发到达目的计算机，网络中的其他计算机不需要对这个数据分组进行检测和判断。
数据库的实施是根据数据库逻辑设计和______设计的结果。
现有如下关系模式：R(教师号，姓名，部门号，部门名称，科研项目编号，项目名称，项目经费，担任工作，完成时间)每名教师可以参加多项科研项目，每个项目可以有多名教师参加，教师参加科研工作包括担任工作及他完成所担任部分的完成时间。(1)根据上述条件，写
假设有一关系模式R(学号，姓名，系名，系主任，课程号，课程名，成绩)其中：每个系只有一位系主任；每个学生学习多门课程，每个课程多个同学选修，每个同学的每门课程只有一个成绩。(1)根据上述条件，写出关系模式R的关键码。(2)R最高属于第几范
有4个关系模式如下：出版社（出版社编号，出版社名称）图书（图书编号，书名，出版社编号，定价）作者（作者编号，姓名）著书（图书编号，作者编号，作者排序）注：作者排序-1表示第一作者，依此类推。用SQL语句，完成小题
把网络节点看作二叉树的叶节点的有限争用协议的是()

随机试题

乳清蛋白受热极易发生变性。
为确定腹腔压痛点常用哪种触诊法
A、血压升高、心率加快B、血压降低、心率加快C、血压升高、心率减慢D、血压降低、心率减慢E、血压和心率均不变肾上腺髓质激素大量释放时
合同转让的类型有()。
客户身份资料自业务关系结束当年计起至少保存________年，与销售业务有关的其他资料自业务发生当年计起至少保存____________年。()
年薪制是以企业()为时间单位，根据经营者的业绩好坏而计发薪酬的一种薪酬制度。
个体工商户、个人独资企业和合伙企业或者个人从事种植业、养殖业、饲养业、捕捞业取得的所得，暂不征收个人所得税。()
17世纪、18世纪的资产阶级学者提出的反映新兴资产阶级利益和要求的思想是()。
下列关于对象"更新前"事件的叙述中，正确的是(　　)。
Itisnotlongsinceconditionsinthemineswereworsethantheyarenow.Therearestill【C1】______afewveryoldwomenwhoin

最新回复(0)

有如下递归函数fact(n)，分析其时间复杂度。 fact(int n) { if(n

数据结构导论

理工类

系统如图所示，G(s)=，其中a=0．4，b=0．5，试求：(1)系统的开环零点及开环极点；(2)系统的闭环零点及闭环极点；(3)系统的阻尼比ζ和无阻尼自然频率ωn。

某单位分配到一个地址块138．24．13．64／26，现在需要进一步划分为8个一样大的子网，则每个子网的网络前缀为多少位?每个子网有多少个IP地址?每个子网的地址块是什么?

IP地址中的网络号所占位数越多，则一个网络内可以容纳的主机数_______。

通信双方可以同时发送和接收信息，这种通信方式称为【】

______是指网络中建立通信的两台计算机之间由一条物理信道相连接，数据分组由源点计算机直接或者经过转发到达目的计算机，网络中的其他计算机不需要对这个数据分组进行检测和判断。

数据库的实施是根据数据库逻辑设计和______设计的结果。

把网络节点看作二叉树的叶节点的有限争用协议的是()

乳清蛋白受热极易发生变性。

为确定腹腔压痛点常用哪种触诊法

A、血压升高、心率加快B、血压降低、心率加快C、血压升高、心率减慢D、血压降低、心率减慢E、血压和心率均不变肾上腺髓质激素大量释放时

合同转让的类型有()。

客户身份资料自业务关系结束当年计起至少保存________年，与销售业务有关的其他资料自业务发生当年计起至少保存____________年。()

年薪制是以企业()为时间单位，根据经营者的业绩好坏而计发薪酬的一种薪酬制度。

个体工商户、个人独资企业和合伙企业或者个人从事种植业、养殖业、饲养业、捕捞业取得的所得，暂不征收个人所得税。()

17世纪、18世纪的资产阶级学者提出的反映新兴资产阶级利益和要求的思想是()。

下列关于对象"更新前"事件的叙述中，正确的是( )。

Itisnotlongsinceconditionsinthemineswereworsethantheyarenow.Therearestill【C1】______afewveryoldwomenwhoin

客户身份资料自业务关系结束当年计起至少保存年，与销售业务有关的其他资料自业务发生当年计起至少保存____年。()

下列关于对象"更新前"事件的叙述中，正确的是(　　)。