全部科目 > 软件设计师 >
2018年上半年 上午试卷 综合知识
第 62 题
知识点 时间复杂性  
章/节 计算机软件知识  
 
 
现需要申请一些场地举办一批活动，每个活动有开始时间和结束时间。在同一个场地，如果一个活动结束之前，另一个活动开始，即两个活动冲突。若活动A从1时间开始，5时间结束，活动B从5时间开始，8时间结束，则活动A和B不冲突。现要计算n个活动需要的最少场地数。
求解该问题的基本思路如下(假设需要场地数为m，活动数为n，场地集合为P1，P2,…,Pm)，初始条件Pi均无活动安排：
(1)采用快速排序算法对n个活动的开始时间从小到大排序，得到活动a1，a2，…，an。对每个活动ai，i从1到n，重复步骤(2)、(3)和(4)；
(2)从P1开始，判断ai与P1的最后一个活动是否冲突，若冲突，考虑下一个场地P2,…；
(3)一旦发现ai与某个Pj的最后一个活动不冲突，则将ai安排到Pj，考虑下一个活动；
(4)若ai与所有已安排活动的Pj的最后一个活动均冲突，则将ai安排到一个新的场地，考虑下一个活动；
(5)将n减去没有安排活动的场地数即可得到所用的最少场地数。
算法首先采用了快速排序算法进行排序，其算法设计策略是( 60 )；后面步骤采用的算法设计策略是( 61 )。整个算法的时间复杂度是( 62 )。下表给出了n=11的活动集合，根据上述算法，得到最少的场地数为( 63 )。
 
  A.  Θ(lgn)
 
  B.  Θ(n)
 
  C.  Θ(nlgn)
 
  D.  Θ(n2)




 
 
相关试题     计算机软件知识 

  第25题    2019年上半年  
某文件系统采用位示图(bitmap)记录磁盘的使用情况。若计算机系统的字长为64位，磁盘的容量为1024GB，物理块的大小为4MB，那么位示图的大小需要（ ）个字。

  第18题    2016年下半年  
某软件项目的活动图如下图所示，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的数字表示相应活动的持续时间（天），则完成该项目的最少时间为（17..

  第48题    2017年下半年  
编译过程中进行的语法分析主要是分析（ ）。

 
知识点讲解
· 时间复杂性
 
        时间复杂性
        算法的时间复杂度分析主要是分析算法的运行时间，即算法所执行的基本操作数。即使对相同的输入规模，数据分布不相同也决定了算法执行不同的路径，因此所需要的执行时间也不相同。根据不同的输入，将算法的时间复杂度分为3种情况。
        （1）最佳情况。使算法执行时间最少的输入。一般情况下，不进行算法在最佳情况下的时间复杂度分析。应用最佳情况分析的一个例子是已经证明基于比较的排序算法的时间复杂度下限为Ω(nlgn)，那么就不需要白费力气去想方设法将该类算法改进为线性时间复杂度。
        （2）最坏情况。使算法执行时间最多的输入。一般会进行算法在最坏时间复杂度的分析，因为最坏情况是在任何输入下运行时间的一个上限，它提供了一个保障，情况不会比这更糟糕。另外，对于某些算法来说，最坏情况还是相当频繁的。而且大致上看，平均情况通常与最坏情况的时间复杂度一样。
        （3）平均情况。算法的平均运行时间。一般来说，这种情况很难分析。举个简单的例子，现要排序10个不同的整数，输入就有10!种不同的情况，平均情况的时间复杂度要考虑每一种输入及其该输入的概率。平均情况分析可以按以下3个步骤进行。
        ①将所有的输入按其执行时间分类。
        ②确定每类输入发生的概率。
        ③确定每类输入的执行时间。
        下式给出了一般算法在平均情况下的复杂度分析，即
        
        式中，pi为第i类输入发生的概率；ti为第i类输入的执行时间，输入分为m类。



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

京B2-20210865 | 京ICP备2020040059号-5
京公网安备 11010502032051号 | 营业执照
 Copyright ©2000-2025 All Rights Reserved
软考在线版权所有