time-complexity - 查找在循环中执行 k += sqrt(k) 的时间复杂度

Question

鉴于此代码:

int f(int n)
{
    int j = 10;
    while( j < n) {
        j += sqrt(j);
        printf("Hello\n");
    }
    return j;
}

我怎样才能找到它的时间复杂度，解决方案是 O(sqrt(n)) 但仍然是为什么？
谢谢你的时间 <3
我能找到的是变量 j 属于一个序列 u
n+1=un+sqrt(un)，试图找到它的通用术语并没有把我带到任何地方，我也尝试过为它使用生成函数，但仍然没有用。

Answer 1

显然，计算 k + 1 的 j -th 值可以表示为函数 f(k + 1) :
(1)
然后，可以通过 f(k + 1) 使用 Taylor series 来近似 f(k) :
(2)
所以，将(2)代入(1)

现在，一旦 f(k) 达到 n ，步数的计算如上，对于这个近似值，时间复杂度是 O(sqrt(n)) 。
现在，让我们通过 k 表示 fk:

那么，一个错误有多严重？请注意，下面使用的 f(k+1) 和 f(k) 是 f(k+1) 和 f(k) 的近似值(来自(1)):

我们不希望错误依赖于 k ，所以我们在它旁边设置了一个系数为 0 。因此，C0=2。

所以，我们的近似误差是 0.25 。
顺便说一下，我们还可以找到一个剩余的系数 C1。为此，我们可以使用 f(0)=10 的初始值。因此，0 = 2 * sqrt(10) + C1 -> C1=-6。