这段代码的重要特征是什么？

Question

有人可以帮我找到这个代码的大O吗？我已经尝试过计算它,但我只是不明白怎么做.

int n = //user input
for (int i = 0; i < n; i++){
    for (int j = 1; j < n; j = j * 2){
        System.out.println(i * j);
    }
}

Answer 1

您应该问自己外循环中有多少次迭代以及内循环中有多少次迭代.然后你将两者相乘.

外部循环很简单 - 我以1为增量从0增长到n-1,因此迭代总数为n,即O(n).

在内部循环中,j从1增长到n-1,但是在每次迭代中j乘以2.如果n = 2 ^ k,对于某些整数k,将存在k次迭代,并且log n = k.因此,内循环中有O(log n)次迭代.

将这两者相乘,得到O(n)*O(log(n))= O(n log(n));