首页 > 试题广场 >

某算法的时间复杂度为O(n2),表明该算法的

[单选题]
某算法的时间复杂度为,表明该算法的
  • 问题规模是n^2
  • 执行时间等于n^2
  • 执行时间与n^2成正相关
  • 问题规模与n^2成正比
推荐
选C。该题考察的是算法时间复杂度的描述概念。
由于受运行环境和输入规模的影响,代码的绝对执行时间无法预估,因此根据通过预估代码的基本操作执行次数来确定时间运行的长短量度,即算法时间复杂度的优劣判断。
  • 时间复杂度的表示无法对问题规模作出预估,而只能对操作次数作出预估,所以A、D错误
  • O(n2)表示的是执行次数是多项式计算的,只保留函数最高阶(平方阶),且去掉系数。并不一定绝对等于n2所以B错误
  • O(n2),当n的值渐增,其算法时间复杂度执行的时间就越长,所以称正比关系。C正确
编辑于 2019-07-10 14:27:38 回复(2)
我觉得都不对。
a显然错误,问题规模指的是n
b也错误,时间复杂度是n2,不代表执行时间就是n2,只是表示比例关系,n2还没单位呢
c是选择上的正确答案,但是时间复杂度是削去了低项的,从数学角度来说成正比表示y=k*(n2),如果要说n趋向于无穷的时候忽略极小项,也可以是一种解释,但是我觉得严格来说不对。
d和a一个意思。
因此,c只能说是错误程度最小的答案
发表于 2021-08-03 17:15:14 回复(1)
此题有问题,C选项也是错误选项,其错误在于错误理解时间复杂度的定义. 

根据算法导论给出的定义,指的是这样的函数集合:存在正常数  和 ,对所有  ,有  只是限定了一个上界,并未要求正比例关系.  

比如一个算法执行时间函数是:, 其时间复杂度表示为. 但该执行时间必定不与  成正比, 因为:,该比值不为常数,即不满足正比关系的定义.

根据定义,还可以取更为特殊的情况:,这个时候怎么可以说 f(n) 与  成正比?



编辑于 2022-03-13 18:04:59 回复(1)
选C
时间复杂度定性的描述了算法的运行时间
问题规模为n,n^2为执行次数的最高项,省略了系数和常数项,所以执行时间不一定等于n^2

发表于 2019-07-09 14:35:33 回复(0)
我单独解释一下答案C为什么正确
首先,有这么一个说法:若存在正的常数c和函数f(n),使得对任何n >> 2都有T(n) <= c * f(n)则可认为在n足够大之后,f(n)给出了T(n)增长速度的一个渐进上界。此时,记为T(n)=O(f(n)).由于题中时间复杂度为O(n^2),所以f(n)=n^2.而执行时间与T(n)同数量级,可以理解为执行时间相当于T(n)而不等于相当于高数中的极限。所以由T(n) <= cn^2,当T(n)=cn^2时,执行时间与n^2成正比。
发表于 2021-09-11 15:03:41 回复(0)