这个程序的时间复杂度模型是什么？

Question

import java.util.Scanner;

public class question {
    public static void main(String[] args) {
        int p = 0;
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        input.close();
        for (int i = 1; i < n; i = i * 2) {
            p++;
        }
        for (int j = 1; j < p; j = j * 2) {
            // statement;
        }
    }
}

我的教授在讲座中问了我们这个问题，我们给出了两个答案：O(log n)和O(log(log n))，但都被他否定了，他留给我们作为思考问题，我想知道正确答案，但想不出其他答案。请帮助我！

抱歉 n 应该是 1!!!!!

Answer 1

~~编辑：我回答这个问题时没有注意到 i 被初始化为 0。仅当问题中所述 i 的初始值是错字时，此答案才是正确的。~~

这两个循环没有嵌套，这意味着您必须将第一个的复杂性加到第二个的复杂性上。

由于第一个循环耗时 O(log(n))，第二个循环耗时 O(log(log(n))，因此总运行时间为 O(log(n)) + O(log(log(n)) = O(log(n))。

第一个循环：

i 从 1 到 n，并在每次迭代中乘以 2。 log₂n次迭代后会达到n，也就是说循环后p的值为log₂ n（或 log₂n - 1）。

第二个循环：

j 从 1 到 log₂n，并且在每次迭代时乘以 2。它会在 log₂(log₂n) 次迭代后达到 log₂n.

Answer 2

此代码包含两个循环，第一个复杂度 O(log(N))，第二个复杂度 O(log(log(N)))。

教授可能希望答案是这两个表达式的总和： O(log(N) + log(log(N)))，尽管第二项要小得多，可以忽略，因此导致 O(log(N))。

Answer 3

可能你的教授想提到输入可能比循环花费更多的时间？我认为 nextint 会读取数字前的空白

这个程序的时间复杂度模型是什么？

What's the time complexity model of this program?

java

algorithm

time-complexity