以下程序的运行时间是多少？

Question

在我的书的行使要我计算循环下的运行时间：

for (int i = 0; i < n; ++i) 
    ++k; 

这立刻让我想起了求和符号的。于是，我写下了适当的语法：

这是正确的吗？如果没有，为什么不 - 我如何正确计算它？

Answer 1

让我们看看循环内的操作：

++k; 

不管是什么k是，该操作将需要一定的时间。所以让我们用O(1)替换它。

for (int i=0; i<n; ++i) 
    O(1) 

我们可以看到，我们将在O(1)块迭代n倍。所以，那就是：

O(n) * O(1) 

其中明确等于：

O(n) 

Answer 2

这是正确的吗？

不是。

如果不是，为什么不 - 我怎样才能正确计算它？

k由1在每个迭代递增的，即当循环终止n被添加到它。因此，k = k + 1不等于k = k + k。

运行代码的时间顺序n因为循环运行n倍，++k在循环内恒定的时间内完成。