具有 1 个循环的函数的复杂性

Question

谁能告诉我下面这个函数的复杂度是多少？以及如何计算复杂度？

我怀疑它是 O(log(n)) 或 O(sqrt(N))。我的推理基于 n=4、n=8、n=16 的示例，我发现循环将采用 log(n) 但我认为这还不够，因为 sqrt 也会给出相同的值所以我需要研究更大的 n 值，所以我不知道如何解决这个问题。

我今天考试的时候有这个功能。

void f(int n){
     int i=1;
     int j=1;
     while(j <= n){
         i += 1;
         j += i;
     }
}

Answer 1

序列j经过1 3 6 10 15 21，又称为三角形数，又称为n*(n+1)/2。

展开来，这是( n^2 + n ) / 2。我们可以忽略缩放 ( / 2) 和线性 ( + n) 因子，从而得到n^2。

j作为多项式增长n^2，因此循环将在该增长的倒数之后停止：

时间复杂度为O(sqrt(n))