找到一個確切的函數，指出該算法所採用的步數

Question

int mystery(int n) { 
    int s = 0; 
    int tmp = n+1; 
    for (int i; i<=n; i++) { 
     s = tmp + i; 
     tmp = s; 
    } 
    return s; 
} 

如何確定該函數以及函數的作用？此外，該功能是否可以在運行時間方面得到改進？

Answer 1

上面有一些多餘的代碼; s是完全不必要的。重寫它沒有它使得它更清晰。

int mystery(int n) { 
    int tmp = n + 1; 
    for (int i = 1; i<=n; i++) { 
     tmp += i; 
    } 
    return tmp; 
} 

它所做的是

• 設置tmp爲N + 1
• 加1，然後2然後3然後4等

這個目前擁有的運行時間O(n)。然而，事實證明1 + 2 + 3 + ... + N有一個constant time formula。我們可以使用它來創建以下，這是不變的時間。

int mystery(int n) { 
    int triangleNumber = (n * (n + 1))/2; 
    return triangleNumber + n + 1; 
}