免费智能真题库
>
历年试卷
>
软件设计师
>
2018年上半年 软件设计师 上午试卷 综合知识
第62题
知识点：
时间复杂性
章/节：
计算机软件知识
现需要申请一些场地举办一批活动，每个活动有开始时间和结束时间。在同一个场地，如果一个活动结束之前，另一个活动开始，即两个活动冲突。若活动A从1时间开始，5时间结束，活动B从5时间开始，8时间结束，则活动A和B不冲突。现要计算
n
个活动需要的最少场地数。
求解该问题的基本思路如下(假设需要场地数为
m，
活动数为
n，
场地集合为
P
1
，
P
2
,…,
P
m
)，初始条件
P
i
均无活动安排：
(1)采用快速排序算法对
n
个活动的开始时间从小到大排序，得到活动
a
1
，
a
2
，…，
a
n
。对每个活动
a
i
，
i
从1到
n，
重复步骤(2)、(3)和(4)；
(2)从
P
1
开始，判断
ai
与
P
1
的最后一个活动是否冲突，若冲突，考虑下一个场地
P
2
,…；
(3)一旦发现
a
i
与某个
P
j
的最后一个活动不冲突，则将
a
i
安排到
P
j
，考虑下一个活动；
(4)若
a
i
与所有已安排活动的
P
j
的最后一个活动均冲突，则将
a
i
安排到一个新的场地，考虑下一个活动；
(5)将
n
减去没有安排活动的场地数即可得到所用的最少场地数。
算法首先采用了快速排序算法进行排序，其算法设计策略是( 60 )；后面步骤采用的算法设计策略是( 61 )。整个算法的时间复杂度是( 62 )。下表给出了
n
=11的活动集合，根据上述算法，得到最少的场地数为( 63 )。
A.
Θ
(lg
n
)
B.
Θ
(
n
)
C.
Θ
(
n
lg
n
)
D.
Θ
(
n
2
)
本题目为专供试卷题目。
【如需要，请开通】
您暂时无法使用本功能。
【如需要，请开通】
为保障您的权益，请登录
相关试题：
计算机软件知识
更多>
第25题
2013年上半年
36%
进程资源图如图(a)和(b)所示，其中：图(a)中（25);图(b)中（26)。
第60题
2017年下半年
45%
以下关于无向连通图G的叙述中，不正确的是（ ）。
第21题
2018年上半年
50%
（21）是一种函数式编程语言。
知识点讲解
·
时间复杂性
时间复杂性
算法的时间复杂度分析主要是分析算法的运行时间，即算法所执行的基本操作数。即使对相同的输入规模，数据分布不相同也决定了算法执行不同的路径，因此所需要的执行时间也不相同。根据不同的输入，将算法的时间复杂度分为3种情况。
（1）最佳情况。使算法执行时间最少的输入。一般情况下，不进行算法在最佳情况下的时间复杂度分析。应用最佳情况分析的一个例子是已经证明基于比较的排序算法的时间复杂度下限为Ω(
n
lg
n
)，那么就不需要白费力气去想方设法将该类算法改进为线性时间复杂度。
（2）最坏情况。使算法执行时间最多的输入。一般会进行算法在最坏时间复杂度的分析，因为最坏情况是在任何输入下运行时间的一个上限，它提供了一个保障，情况不会比这更糟糕。另外，对于某些算法来说，最坏情况还是相当频繁的。而且大致上看，平均情况通常与最坏情况的时间复杂度一样。
（3）平均情况。算法的平均运行时间。一般来说，这种情况很难分析。举个简单的例子，现要排序10个不同的整数，输入就有10!种不同的情况，平均情况的时间复杂度要考虑每一种输入及其该输入的概率。平均情况分析可以按以下3个步骤进行。
①将所有的输入按其执行时间分类。
②确定每类输入发生的概率。
③确定每类输入的执行时间。
下式给出了一般算法在平均情况下的复杂度分析，即
式中，
p
i
为第
i
类输入发生的概率；
t
i
为第
i
类输入的执行时间，输入分为
m
类。
题号导航
2018年上半年 软件设计师 上午试卷 综合知识
本试卷我的完整做题情况
1
/
2
/
3
/
4
/
5
/
6
/
7
/
8
/
9
/
10
/
11
/
12
/
13
/
14
/
15
/
16
/
17
/
18
/
19
/
20
/
21
/
22
/
23
/
24
/
25
/
26
/
27
/
28
/
29
/
30
/
31
/
32
/
33
/
34
/
35
/
36
/
37
/
38
/
39
/
40
/
41
/
42
/
43
/
44
/
45
/
46
/
47
/
48
/
49
/
50
/
51
/
52
/
53
/
54
/
55
/
56
/
57
/
58
/
59
/
60
/
61
/
62
/
63
/
64
/
65
/
66
/
67
/
68
/
69
/
70
/
71
/
72
/
73
/
74
/
75
/
第62题 在手机中做本题
