单选题
某算法的时间复杂度可用递归式 [*] 表示,若用Θ表示该算法的渐进时间复杂度的紧致界,则正确的是______。
A、
Θ(nlg
2
n)
B、
Θ(nlgn)
C、
Θ(n
2
)
D、
Θ(n
2
)
【正确答案】
A
【答案解析】
在本题中,我们关键要理解算法的渐进紧致界的概念,举个例子来说吧,假设当N>N
0
时,函数f(N)在一个常数因子范围内等于g(N),则称g(n)是f(n)的一个渐进紧致界。
[*]
本题中给出的递归式的渐进紧致界应该是A。
提交答案
关闭