我有点困惑的下面的代码段的时间复杂度的环的复杂性(极限是硬编码的报价为例):时间随增量
loss = 3;
for(i=0;i<=10;)
{
i += loss;
loss = loss - 0.3; //loss keeps decreasing by some fixed value
}
这里,尽管可变i
正在不断增加接近终止循环,但它增加的速度本身是可变的。
我有点困惑的下面的代码段的时间复杂度的环的复杂性(极限是硬编码的报价为例):时间随增量
loss = 3;
for(i=0;i<=10;)
{
i += loss;
loss = loss - 0.3; //loss keeps decreasing by some fixed value
}
这里,尽管可变i
正在不断增加接近终止循环,但它增加的速度本身是可变的。
在此特定示例中,时间复杂度为O(1)
,因为由于它没有参数,所以执行时总是需要相同的时间。
如果这个数字10
在for循环参数n
这将是O(n)
一个小n
,如果n
是足够大的“损失”最终将成为负,程序会永远运行下去。 “损失”以不变的数量影响时间复杂性。
它不会是O(n) - 对于大n,写入的代码不会终止。 –
@保尔绝对正确,“损失”最终会是负面的,它会永远运行 – Davide
如果用大数代替“10”,则循环将永远不会终止,因为在某个时刻'loss'将变为负数。 –