首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
某算法的时间复杂度为O(n2),表明该算法的
[单选题]
某算法的时间复杂度为
,表明该算法的
问题规模是n^2
执行时间等于n^2
执行时间与n^2成正相关
问题规模与n^2成正比
查看答案及解析
添加笔记
邀请回答
收藏(95)
分享
5个回答
添加回答
7
推荐
白驹之过隙
选C
。该题考察的是算法时间复杂度的描述概念。
由于受运行环境和输入规模的影响,代码的绝对执行时间无法预估,因此根据通过预估代码的
基本操作
执行次数
来确定时间运行的长短量度,即算法时间复杂度的优劣判断。
时间复杂度的表示无法对
问题规模作出预估
,而只能对
操作次数
作出预估,
所以A、D错误
。
O(n
2
)表示的是执行次数是
多项式
计算的,只保留函数
最高阶(平方阶),且去掉系数。并不一定绝对等于
n
2
,
所以B错误
。
O(n
2
),当n的值渐增,其算法时间复杂度执行的时间就越长,所以称正比关系。
C正确
。
编辑于 2019-07-10 14:27:38
回复(2)
4
玄成
我觉得都不对。
a显然错误,问题规模指的是n
b也错误,时间复杂度是n2,不代表执行时间就是n2,只是表示比例关系,n2还没单位呢
c是选择上的正确答案,但是时间复杂度是削去了低项的,从数学角度来说成正比表示y=k*(n2),如果要说n趋向于无穷的时候忽略极小项,也可以是一种解释,但是我觉得严格来说不对。
d和a一个意思。
因此,c只能说是错误程度最小的答案
发表于 2021-08-03 17:15:14
回复(1)
2
AntonIsLoading
此题有问题,C选项也是错误选项,其错误
在于错误理解时间复杂度的
定义.
根据算法导论给出的定义,
指的是这样的函数集合:存在正常数
和
,对所有
,有
.
只是限定了一个上界,并未要求正比例关系.
比如一个算法执行时间函数是:
, 其时间复杂度表示为
. 但该执行时间必定不与
成正比, 因为:
,该比值不为常数,即不满足正比关系的定义.
根据定义,还可以取更为特殊的情况:
,这个时候怎么可以说
与
成正比?
编辑于 2022-03-13 18:04:59
回复(1)
1
天降奥佛
选C
时间复杂度定性的描述了算法的运行时间
问题规模为n,n^2为执行次数的最高项,省略了系数和常数项,所以执行时间不一定等于n^2
发表于 2019-07-09 14:35:33
回复(0)
0
牛客976476112号
我单独解释一下答案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)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
复杂度
上传者:
星辰大海的碎片
难度:
5条回答
95收藏
25462浏览
热门推荐
相关试题
数据链路层滑动窗口机制中发送窗口(...
网络基础
评论
(1)
供受文者使用的具有法定效用的正式文...
京东
产品运营
2018
常识判断
行政
评论
(1)
有关linux线程的描述,正确的是...
京东
Java工程师
C++工程师
iOS工程师
安卓工程师
运维工程师
前端工程师
算法工程师
PHP工程师
2018
评论
(1)
用一种动物介绍你自己
通用能力
评论
(1)
请你说几个海量数据存储常见问题以及...
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题