確定此函數的Big-O增長率

Question

我無法確定如何確定這些類型函數的增長率。

void A(int n){ 
int i=1, s=1; 
while(s<=n){ 
    i++; 
    s=s+i; 
    cout<<"hi"; 
    } 
} 

它被認爲是O（sqrt（n）），但我不知道如何？

Answer 1

如果你看看每次迭代的s值，你會發現它變爲1,3,6,10,15等。這些數字被稱爲三角形數字，它們是形式k（ k + 1）/ 2（通常將其證明爲感應練習。）

只要s超過n，循環就停止運行。在迭代k中，s的值爲k（k + 1）/ 2，所以你可以通過求解k（k + 1）/ 2中的k來計算迭代次數。嘗試做到這一點，看看你找到了什麼。這是否解釋了平方根？