确定此函数的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来计算迭代次数。尝试做到这一点，看看你找到了什么。这是否解释了平方根？