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

admin2019-06-12 32

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

选项 A、O(lgn)
B、O(nlgn)
C、O(n)
D、O(n²)

答案B

解析递推关系式T(n)=2T(n／2)n其实是在给n个元素进行快速排序时最好情况(每次分割都恰好将记录分为两个长度相等的子序列)下的时间递推关系式，其中T(n／2)是一个子表需要的处理时间，n为当次分割需要的时间。注意，这里实际上是用比较次数来度
量时间。可以对此表达式进行变形得

用n／2代替上式中的n可得

继续用n／2代替上式中的n可得

算法共需要进行[1bn]+1次分割(n个元素的序列的对半分割树的高度跟具有n个结点的完全二叉树高度相等，软设级别的只需知道即可，不必深究)，将上述[1bn]+1个式子相加，删除相互抵消的部分得

而T(1)=1，那么上式可转化为
T(n)=n[1bn]+2n
而在求时间复杂度时关注“大头”，注意到O(n)T(n)=O(nlogn)=O(nlgn)
数学上，一般将底为10的对数简略写成lgn。

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

在进行进度安排时，PERT图不能清晰地描述(1)，但可以给出哪些任务完成后才能开始另一任务。某项目X包含任务A、B、…、J，其PERT如下图所示(A=1表示该任务A的持续时间是1天)，则项目X的关键路路径是(2)。(2013年上半年试题)(2)

以下关于在IPv6中任意播地址的叙述中，错误的是_____________。

在以太网协议中使用1-坚持型监听算法的特点是(62)。

防火墙的工作层次是决定防火墙效率及安全的主要因素，下面的叙述中正确的是(44)。

阅读下列Java程序和程序说明，将应填入(n)处的字句写在对应栏内。【说明】StringEditor类的功能是：已知一个字符串，返回将字符串中的非字母字符都删除后的字符串。public(1){publicstati

请补充函数fun()，该函数的功能是将字符串tt中的大写字母都改为对应的小写字母，其他字符不变。例如，若输入“AreyoucomefromSichuan?”，则输入“areyoucomefromsi-chuan?”。注意：部分源程

请补充函数fun()，该函数可以统计一个长度为n的字符串在另一个字符串中出现的次数。例如，假定输入的字符串为：asdascasdfgasdasasdmlosd，子字符串为asd，则应输出4。注意：部分源程序给出如下。请勿改动主函数

戈那瑞林的临床应用注意事项有

减少假性神经递质形成的药物是

发生质量事故后，由项目法人负责组织有关单位制定处理方案的有（）。

预应力钢筋混凝土应优先采用硅酸盐水泥，不宜使用（）水泥。

案例七：黄先生在北京购买了一套价值100万元的普通住宅。根据案例七，回答下列问题：如果黄先生是通过向商业银行贷款买房的，则他与商业银行签订《个人购房贷款合同》时，所缴纳的印花税为(　　)元。

债券发行人的信用度越低，投资者所要求的收益率越低。(　　)

下列有关差错的会计处理中，符合现行会计准则规定的有()。

以下不属于人工智能领域的Python第三方库是()。

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

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

软考中级

在进行进度安排时，PERT图不能清晰地描述(1)，但可以给出哪些任务完成后才能开始另一任务。某项目X包含任务A、B、…、J，其PERT如下图所示(A=1表示该任务A的持续时间是1天)，则项目X的关键路路径是(2)。(2013年上半年试题)(2)

以下关于在IPv6中任意播地址的叙述中，错误的是_____________。

在以太网协议中使用1-坚持型监听算法的特点是(62)。

防火墙的工作层次是决定防火墙效率及安全的主要因素，下面的叙述中正确的是(44)。

阅读下列Java程序和程序说明，将应填入(n)处的字句写在对应栏内。【说明】StringEditor类的功能是：已知一个字符串，返回将字符串中的非字母字符都删除后的字符串。public(1){publicstati

请补充函数fun()，该函数的功能是将字符串tt中的大写字母都改为对应的小写字母，其他字符不变。例如，若输入“AreyoucomefromSichuan?”，则输入“areyoucomefromsi-chuan?”。注意：部分源程

请补充函数fun()，该函数可以统计一个长度为n的字符串在另一个字符串中出现的次数。例如，假定输入的字符串为：asdascasdfgasdasasdmlosd，子字符串为asd，则应输出4。注意：部分源程序给出如下。请勿改动主函数

戈那瑞林的临床应用注意事项有

减少假性神经递质形成的药物是

发生质量事故后，由项目法人负责组织有关单位制定处理方案的有（）。

预应力钢筋混凝土应优先采用硅酸盐水泥，不宜使用（）水泥。

案例七：黄先生在北京购买了一套价值100万元的普通住宅。根据案例七，回答下列问题：如果黄先生是通过向商业银行贷款买房的，则他与商业银行签订《个人购房贷款合同》时，所缴纳的印花税为( )元。

债券发行人的信用度越低，投资者所要求的收益率越低。( )

下列有关差错的会计处理中，符合现行会计准则规定的有()。

以下不属于人工智能领域的Python第三方库是()。

案例七：黄先生在北京购买了一套价值100万元的普通住宅。根据案例七，回答下列问题：如果黄先生是通过向商业银行贷款买房的，则他与商业银行签订《个人购房贷款合同》时，所缴纳的印花税为(　　)元。

债券发行人的信用度越低，投资者所要求的收益率越低。(　　)