以下程序的運行時間是多少？

在我的書的行使要我計算循環下的運行時間：以下程序的運行時間是多少？

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

這立刻讓我想起了求和符號的。於是，我寫下了適當的語法：

enter image description here

這是正確的嗎？如果沒有，爲什麼不 - 我如何正確計算它？

所有你在這裏做計數。如果我理解你的練習陳述，那麼它與測量時間有關。爲此，您需要使用高精度時鐘功能。 – Logicrat 2014-09-06 20:58:25

讓我們看看循環內的操作：

++k;

不管是什麼k是，該操作將需要一定的時間。所以讓我們用O(1)替換它。

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

我們可以看到，我們將在O(1)塊迭代n倍。所以，那就是：

O(n) * O(1)

其中明確等於：

O(n)

2014-09-06 20:59:19

在我所關注的書中，我們沒有使用'O'語法。我們打破代表代碼的方程式。所以在這種情況下，它就像我的問題中的總結符號。 – 2014-09-06 21:02:49

也許你的書正在尋找'\ sum_ {i = 1}^{n} 1'？但我只能幫助我知道的符號。如果你想閱讀這個符號，[這裏是維基百科鏈接]（https://en.wikipedia.org/wiki/Big_O_notation）。 – 2014-09-06 21:04:23

您的代碼正在求和'1 + 1 + 1 + ...''n'次。我的代碼添加了'k + 1 + 1 ...' - 'k'不保證從'1'開始。 – 2014-09-06 21:07:11

這是正確的嗎？

不是。

如果不是，爲什麼不 - 我怎樣才能正確計算它？

k由1在每個迭代遞增的，即當循環終止n被添加到它。因此，k = k + 1不等於k = k + k。

運行代碼的時間順序n因爲循環運行n倍，++k在循環內恆定的時間內完成。

2014-09-06 20:58:51 haccks

回答