java - 算法运行时间分析

Question

big-O 运行时间是多少？我主要对 while 循环运行时间感到困惑。我知道两个 for 循环的运行时间都是 O(n)。

cin >> n >> min >> max;

for(int i = min; i < n; i++) {

     for(int j = 1; j < max; j++) {

        total = 1;

        while(total < n) {

             total = total *2;

        }

    }
}

Answer 1

target 在while 循环中的进程是:

1 2 4 8 ... 2^P

您需要 log(2, n) 个步骤——即 log of n in base 2。该循环是 O(log n)。