data-structures - Big O 表示法的时间复杂度

Question

我需要找到某个函数的时间复杂度，而且我不确定我是否正确。

让我们来看看：

f(int i){
    Int x = 1;
    While(x > i){
        System.out.println(x);
        x=x*2;
    }

    While(x > 2){
        x = (int) Math.pow(x,1/2);
        System.out.println(x);
    }
}

现在，我认为第一个 while 循环告诉我们 x = log(i);

第二个循环取决于 x，她在每次迭代中取 x 的值：

x^1/2 + x^1/4 + ••• + x^1/(2^k)。

假设第二个循环在 x<=2 时停止，因此她运行：

(Log(i))^1/(2^k) 并且在对数规则之后我们发现是 O(loglog(n))

标签： data-structuresbig-o

Answer 1

假设第一个循环是while(x < 1).

• 第一个循环是log(n).
• 第二个循环是log(log(n))。

第一个循环占主导地位，所以我会说函数f()具有log(n)复杂性。