下面函数中渐进时间最小的是(53)。A．T1(n)=n+nlognB．T2(n)=2n+nlognC．T3(n)=n2-lognD．T4(n)=n+100logn
题目
下面函数中渐进时间最小的是(53)。
A．T1(n)=n+nlogn
B．T2(n)=2n+nlogn
C．T3(n)=n2-logn
D．T4(n)=n+100logn
相似考题
更多“下面函数中渐进时间最小的是(53)。A.T1(n)=n＋nlognB.T2(n)=2n＋nlognC.T3(n)=n2－lognD.T4(n)=n＋100 ”相关问题
-
第1题：
下面函数中渐进时间最小的是(51)。
A．T1(n)=n+nlogn
B．T2(n)=2n
C．T3(n)=n2-logn
D．T4(n)=n+100logn
正确答案：D
解析：显然T4(n)=n+100logn渐进时间最小。 -
第2题：
关于下面函数,哪一个是错误描述?n为整数defsum(n):ifn<=0:return0returnn＋sum(n－1)A.功能等价于下面的函数#n为整数defsum2(n):return(1+n)*n/2
B.sum(5)是函数调用
C.是递归函数
D.求任意两个数值n和n-1的和
正确答案：D
-
第3题：
13、假设sqrt（n)函数中涉及的算法时间复杂度为O（1)，那么下面的算法是判断n是否为素数，其时间复杂度为（）。 void prime（int n) { for （i=2; i＜sqrt（n) && （n % i)!=0; i++) ; if （i＞sqrt（n)) printf（"%d is a prime number", n); else printf（"%d is not a prime number", n); }
A．O(n)
B．O(1)
C．O(sqrt(n)) sqrt表示对n取根方
D．O(n-i)
(1)解: 设新机器用同一算法在t秒内能解输入规模为n‘的问题 则t=3* =3* /64, 计算n'=n+6 -
第4题：
以下函数中渐进时间最小的是(44)。
A．T1(n)=2n+nlogn
B．T2(n)=n+10 000logn
C．T3(n)=2n+nlogn
D．T4(n)=n2+nlogn
正确答案：B
解析：通常情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记做T(n)=O(f(n))。它表示随问题规模n的增大，算法执行的时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度。当n→∞时，常见的渐进时间复杂度大小关系如下。O(1)≤O(n)≤O(nlogn)≤O(n2)由此可知，试题中所给出的4个函数中，函数T2(n)=n+10000logn的渐进时间最小。 -
第5题：
假设sqrt（n)函数中涉及的算法时间复杂度为O（1)，那么下面的算法是判断n是否为素数，其时间复杂度为（）。 void prime（int n) { for （i=2; i＜sqrt（n) && （n % i)!=0; i++) ; if （i＞sqrt（n)) printf（"%d is a prime number", n); else printf（"%d is not a prime number", n); }
A．O(n)
B．O(1)
C．O(sqrt(n)) sqrt表示对n取根方
D．O(n-i)
以上都不对