此代碼的最壞情況？

Question

n = 0; 
sum = 0; 
cin >> x; 
while (x != -999) 
{ 
    n++; 
    sum += x; 
    cin >> x; 
} 
mean = sum/n; 

我明白如何找到算法的複雜性。 我的問題是，我不確定這是否可以解決，因爲它依賴於輸入。 對於最壞的情況，我認爲輸入不會等於-999，所以最壞的情況複雜度是無窮大。 這是正確的方式去做這件事嗎？提前致謝！！

Answer 1

執行此算法所用的時間與輸入數量呈線性關係。如果有無限輸入（從不-999），則需要無限時間。但它仍然是O（n）。

Answer 2

你說得對，解決這個問題是不可能的。在這種情況下，我會說這是最佳案例場景如果您的輸入滿足條件。在大多數情況下，循環將永遠持續下去，即使包含變量溢出，x等於-999（並且溢出意味着用戶輸入非常大的數字然後解析爲負數）的可能性很小。

爲了複雜性理論，該算法的運行時間爲O(k)，其中k表示循環執行的次數。假設它是無限的，這很好。