無法理解算法中的執行時間

Question

我很難確定算法中每個步驟的執行時間。我無法理解這個邏輯。我們都知道在算法中確定Big O或Theta之前，我們必須計算每一步的執行時間，然後根據執行時間來計算順序。

我覺得比大O或theta計算順序更容易，但我的問題是計算執行時間。

實施例：

for i=0 to **n** 

dothisStep 

的這個執行時間是：（N + 1），這使得它的O（N）的命令 - 這是一個容易和我理解why--我的問題是「較難的」。有時我應該得到n（n + 1）/ 2，有時n（n + 1），但我只是不明白如何或爲什麼！什麼是規則？

Answer 1

我認爲在這些問題的幫助下你會在這裏想到當n接近無窮大時會發生什麼。在n + 1的例子中，+ 1相對於n變得非常微不足道。

您的其他示例：n(n+1) - 再次，當n接近無限時添加1非常微不足道，因此我們刪除+ 1。這留下了n(n)這是n^2。