A.算法的时间复杂度,是指它在某台计算机上具体实现时的运行时间
B.算法的时间复杂度,是指对于该算法的一种或几种主要的运算,运算的次数与问题的规模之间的函数关系
C.一个问题如果是NPC类的,就意味着在解决该问题时,不存在一个具有多项式时间复杂度的算法。 但这一点还没有得到理论上的证实,也没有被否定
D.一个问题如果是NP类的,与C有相同的结论
第1题
下面说法中错误的是()。
①算法原地工作的含义是指不需要任何额外的辅助空间
②在相同问题规模n下时间复杂度为O(n)的算法总是优于时间复杂度为O(2n)的算法.
③所谓时间复杂度是指在最环情形下估算算法执行时间的-一个上界
④同一个算法,实现语言的级别越高,执行效率越低
A、①
B、①②
C、①④
D、③
第5题
有实现同一功能的两个算法():和(),其中(),的渐进时间复杂度T1(n)=O(2n),A2的渐进时间复杂度是T2(n)=()(n2)。仅就时间复杂度面言,具体分析这两个算法哪个好。
第8题
已知有实现同一功能的两个算法,其时间复杂度分别为O(2n)和O(n10),假设计算机可连续运算的时间为107秒(100多天),又每秒可执行基本操作(根据这些操作来估算算法时间复杂度)105次,试问在此条件下,这两个算法可解问题的规模(即n值的范围)各为多少?哪个算法更适宜?请说明理由。
第10题
设求解某问题的递归算法如下:
求解该算法的计算时间时,仅考虑算法Move所做的计算,且Move为常数级算法。则算法F的计算时间T(n)的递推关系式为()。
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
为了保护您的账号安全,请在“上学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!