Question

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

某算法的时间复杂度为O(n),表明该算法的：
A.问题规模是n
B.执行时间等于n
C.执行时间与n成正比
D.问题的规模与n成正比
能能都解释下呀？

Answer 1

C、执行时间与n成正比。

A选项，算法的时间复杂度与问题规模没有任何关系。故A选项错误。

B选项，任何算法的执行时间都几乎不可能完全等于。故B选项错误。

C选项，如果一个算法的时间复杂度为，的值增加，的值也会随之增加，那么执行时间肯定就是与成正比的。故C选项正确。

D选项，一个算法的时间复杂度与这个问题的数据规模没有关系，故D选项也错误。

扩展资料：

算法的时间复杂度通常用大O符号表述，定义为T[n] = O(f(n))。称函数T(n)以f(n)为界或者称T(n)受限于f(n)。

如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。

Answer 2

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为t(n)。
t(n)=o(n*n)的意思就是算法大概执行n的平方次，时间与执行次数成正比。，问题规模还是n。
跟o（）没有关系。

Answer 3

选c
说明算法的时间复杂度Tn小于等于cn（c为比例常数），即Tn＝o(n)，时间复杂度是问题规模n的函数。

Answer 4

n就是问题的规模，因此A答案不对，答案是C，时间复杂度就是执行时间，O代表同数量级，至于答案B，则是C中包含的特例，一般O(n^2)得算法并不一定是执行时间等于n^2

追问

不是n^2呀