算法的时间复杂性，可以表达为关于问题规模n的一个函数T（n)，T（n)可以用大O表示法来处理。问T（n)=O（f（n))是什么意思？正确的是_________。A．T(n)是关于f(n)的一个函数。B．T(n)是与f(n)同数量级的函数。C．T(n)是将函数f(n)代入O(x)中所形成的新函数。D．T(n)是依据f(n)计算出来的。
题目
算法的时间复杂性，可以表达为关于问题规模n的一个函数T（n)，T（n)可以用大O表示法来处理。问T（n)=O（f（n))是什么意思？正确的是_________。
A．T(n)是关于f(n)的一个函数。
B．T(n)是与f(n)同数量级的函数。
C．T(n)是将函数f(n)代入O(x)中所形成的新函数。
D．T(n)是依据f(n)计算出来的。
相似考题
更多“算法的时间复杂性，可以表达为关于问题规模n的一个函数T（n)，T（n)可以用大O表示法来处理。问T（n)=O（f（n))是什么意思？正确的是_________。”相关问题
-
第1题：
假设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n，T(1)=1表示，则该算法的时间复杂度为()
A.O(logn)
B.O(n*logn)
C.O(n)
D.O(n^2)
正确答案：B
-
第2题：
某算法的时间代价递推关系为T(n)=2T(n/2)+n，T(1)=1，则该算法的时间复杂度为______。
A．O(n)
B．
C．O(n2)
D．O(1)
正确答案：B
解析：由时间代价严格推出时间复杂度比较复杂，对于这种题，可用特例验证，不过需要注意的是特例不能取太少，至少n取到5，这样规律基本就可以确定了。
T(1)=1
T(2)=2T(1)+2=4
T(3)=2T(1)+3=5
T(4)=2T(2)+4=12
T(5)=2T(2)+5=13
很容易排除D选项，其递增速率介于O(n)和O(nsup>2</sup>)之间，故选B。 -
第3题：
设某算法的计算时间表示为递推关系式T(n)＝T(n-1)+n(n＞O)及T(0)＝1，则该算法的时间复杂度为(65)。
A．O(lgn)
B．O (nlgn)
C．O(n)
D．O(n2)
正确答案：D
解析：本题考查算法设计基础知识。根据题目中给出的递推关系：T(n)＝T(n-1)+n＝T(n-2)+n-1+n＝…＝T(0)+1+2+…+n-1+n＝1+n(n+1)/2 -
第4题：
设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n表示，则该算法的时间复杂度为(1)。
A．O(lgn)
B．O(nlgn)
C．O(n)
D．O(n2)
正确答案：B
解析：运用数学递推公式，可以推算出数量级O(nlgn)。 -
第5题：
已知算法A的运行时间函数为T（n）=8T（n/2）+n2，其中n表示问题的规模，则该算法的时间复杂度为（ ）A.θ（n）
B.θ（nlgn）
C.θ（n2）
D.θ（n3）答案：D解析：本题需要用到特定形式的递归式分析法：
在本题中，a=8,b=2，故符合（1）的情况。时间复杂度为：O（n3）。a=16,b=4 -
第6题：
设某算法的计算时间表示为递推关系式T（n）＝T（n-1）+n（n＞O）及T（0）＝1，则该算法的时间复杂度为（ ）。A.O（lgn）
B.O（nlgn）
C.O（n）
D.O（n^2）答案：D解析：本题考查算法设计基础知识。根据题目中给出的递推关系：T（n）＝T（n-1）+n＝T（n-2）+n-1+n＝…＝T（0）+1+2+…+n-1+n＝1+n（n+1）/2 -
第7题：
设T（n）=n，根据T（n）=O（f（n））的定义，O（n2）=T（n）。
正确答案:错误 -
第8题：
数据结构里，时间复杂度记作：（）。
- A、T（n）=O（f（n））
- B、S（n）=O（f（n））
- C、T（n）=f（n）
- D、S（n）=f（n）
正确答案:A -
第9题：
下面程序的时间复杂度为（）。 for（i=0；i
- A、O（m×n×t）
- B、O（m+n+t）
- C、O（m+n×t）
- D、O（m×t+n）
正确答案:A -
第10题：
设T（n）=n，根据T（n）=O（f（n））的定义，T（n）=O（logn）+O（n）。
正确答案:正确 -
第11题：
判断题设T（n）=n，根据T（n）=O（f（n））的定义，T（n）=O（logn）+O（n）。A对
B错
正确答案： 错解析： 暂无解析 -
第12题：
判断题设T（n）=n，根据T（n）=O（f（n））的定义，T（n）=O（n2）。A对
B错
正确答案： 错解析： 暂无解析 -
第13题：
T(n)=O(f(n))中，函数O()的正确含义为
A.T(n)为f(n)的函数
B.T(n)为n的函数
C.存在足够大的正整数M，使得T(n)≤M×f(n)
D.存在足够大的正整数M，使得M×f(n)≤T(n)
正确答案：C
-
第14题：
若n表示问题的规模、O(f(n))表示算法的时间复杂度随n变化的增长趋势，则算法时间复杂度最小的是(59)。
A．O(n2)
B．O(n)
C．O(logn)
D．O(nlogn)
正确答案：C
解析：本题考查的是算法消耗的时间度量。一般情况下，一个算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n))，它表示随问题n的增大，算法执行时间的增长率和 f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。显然，在O(n2)、O(n)、 O(logn)和O(nlogn)中，复杂度最小的是O(logn)。 -
第15题：
设求解某问题的递归算法如下：
F(int n){
if n=1 {
Move(1)
}else{
F(n-1)；
Move(n)；
F(n-1)；
}
}
求解该算法的计算时间时，仅考虑算法Move所做的计算为主要计算，且Move为常数级算法。则算法F的计算时间T(n)的递推关系式为(9)；设算法Move的计算时间为k，当 n=4时，算法F的计算时间为(10)。
A．T(n)=T(n-1)+1
B．T(n)=2T(n-1)
C．T(n)=2T(n-1)+1
D．T(n)=2T(n+1)+1
正确答案：C
-
第16题：
某个算法的时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为 （请作答此空） ，若问题的规模增加了16倍，则运行时间增加 （ ） 倍。A.O(n)
B.O(nlgn)
C.O(n2)
D.O(n2lgn)答案：C解析：对于递归式，假设T(1)=1，则：
T(n)=T(n-1)+n
=T(n-2)+n-1+n
=T(n-3)+n-2+n-1+n
=1+2+…+n-1+n
=n(n+1)/2
可见，时间复杂度为O(n2)。若问题的规模增加了16倍，则运行时间增加了162=256倍。 -
第17题：
已知算法A的运行时间函数为T（n）=8T（n/2）+n2，其中n表示问题的规模，另已知算法B的运行时间函数为T（n）=XT（n/4）+n2，其中n表示问题的规模。对充分大的n，若要算法B比算法A快，则X的最大值为（ ）。A.15
B.17
C.63
D.65答案：C解析：本题需要用到特定形式的递归式分析法：
在本题中，a=8,b=2，故符合（1）的情况。
时间复杂度为：O（n3）。
a=16,b=4 -
第18题：
某个算法的时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为（62），若问题的规模增加了16倍，则运行时间增加（63）倍。A.O(n)
B.O(nlgn)
C.O(n2)
D.O(n2lgn)答案：C解析：对于递归式，假设T(1)=1，则：
T(n)=T(n-1)+n
=T(n-2)+n-1+n
=T(n-3)+n-2+n-1+n
=1+2+…+n-1+n
=n(n+1)/2
可见，时间复杂度为O(n2)。若问题的规模增加了16倍，则运行时间增加了162=256倍。 -
第19题：
T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是（）
- A、T（n）=T（n–1）+1，T（1）=1
- B、T（n）=2n2
- C、T（n）=T（n/2）+1，T（1）=1
- D、T（n）=3nlog2n
正确答案:C -
第20题：
时间复杂度记为：T（n）=O（f（n））；其中n是（）。
- A、函数
- B、问题的规模
- C、渐近符号
- D、规模的函数
正确答案:B -
第21题：
算法的时间复杂度记为：T（n）=O（f（n））。
正确答案:正确 -
第22题：
单选题T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是（）AT（n）=T（n–1）+1，T（1）=1
BT（n）=2n2
CT（n）=T（n/2）+1，T（1）=1
DT（n）=3nlog2n
正确答案： D解析： 暂无解析 -
第23题：
判断题算法的时间复杂度记为：T（n）=O（f（n））。A对
B错
正确答案： 对解析： 暂无解析 -
第24题：
单选题时间复杂度记为：T（n）=O（f（n））；其中n是（）。A函数
B问题的规模
C渐近符号
D规模的函数
正确答案： C解析： 暂无解析