2016-12-15 466 views
2

我有点困惑的下面的代码段的时间复杂度的环的复杂性(极限是硬编码的报价为例):时间随增量

loss = 3; 
for(i=0;i<=10;) 
{ 
    i += loss; 
    loss = loss - 0.3; //loss keeps decreasing by some fixed value 
} 

这里,尽管可变i正在不断增加接近终止循环,但它增加的速度本身是可变的。

+1

如果用大数代替“10”,则循环将永远不会终止,因为在某个时刻'loss'将变为负数。 –

回答

0

在此特定示例中,时间复杂度为O(1),因为由于它没有参数,所以执行时总是需要相同的时间。

如果这个数字10在for循环参数n这将是O(n)一个小n,如果n是足够大的“损失”最终将成为负,程序会永远运行下去。 “损失”以不变的数量影响时间复杂性。

+1

它不会是O(n) - 对于大n,写入的代码不会终止。 –

+0

@保尔绝对正确,“损失”最终会是负面的,它会永远运行 – Davide