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

brc7rcf0 于 2021-07-11 发布在 Java

关注(0)|答案(3)|浏览(264)

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（logn）和o（logn）），但是都被他否认了，他把它作为一个思考的问题留给了我们，我想知道正确的答案，但是没有其他的答案。请帮帮我！
对不起，n应该是1！！！！！

Java Algorithm time-complexity

来源：https://stackoverflow.com/questions/64953542/whats-the-time-complexity-model-of-this-program

3条答案

按热度按时间

8zzbczxx1#

编辑：我没注意就回答了这个问题 i 已初始化为 0 . 只有在下列情况下，这个答案才是正确的 i 问题中提到的初始值是一个拼写错误。
这两个循环不是嵌套的，这意味着您必须将第一个循环的复杂性添加到第二个循环的复杂性中。
因为第一个循环 O(log(n)) 第二个是 O(log(log(n)) ，总运行时间为 O(log(n)) + O(log(log(n)) = O(log(n)) .
第一个回路：
i从1到n，每次迭代都乘以2。它将到达 n 在log2n迭代之后，也就是在循环之后 p 的值是log2n（或log2n-1）。
第二个回路：
j从1到log2n，在每次迭代中乘以2。它将在log2（log2n）迭代之后到达log2n。