Time/Algorithm 复杂性 - 嵌套，同时按产品递增 - 模式

Question

我正在尝试测量算法的时间复杂度。该算法有一段时间内有一段时间，从1开始。好的。但问题是 i 随着产品的增加而增加。我没有使用大 O，只计算指令。我正在寻找一种模式。

在这个例子中，我做对了：

i = 1; -> // 1 execution
while(i<=n) { // n+1
  j =1; // n
while(j<=n) { // n²
....
  j = j + 1; // n² * 2
}
i = i + 1; // 2n
}

好的。我只需要总结一下。

但问题出在这种情况下：

i = 1; // 1 execution
while(i<n) { // n execution?
System.out.println("*"); // n execution?              
i = i * 2; // n execution????
}

我测试了太多方法：

When n is 2 ---> The println run 1 time.
When  n is  3 ---> The println run 2 times.
When n is 4 ---> The println run 2 times.
When n is 5 ---> The println run 3 times.
When n is 6 ---> The println run 3 times.

模式是什么？

我不想使用大 O 表示法。

Answer 1

复杂度为 O(log(n)) 因为我们在每次迭代中将 i 除以 2 所以假设 while 循环将执行 m 次它们我们有 2^m<=n 这意味着 m<=log(n) 所以它是 O(log(n)).

Time/Algorithm 复杂性 - 嵌套，同时按产品递增 - 模式

Time/Algorithm Complexity - Nested while Incremented by a product - pattern

big-o

time-complexity

asymptotic-complexity