i=i*2的for循环运行时间分析：外层循环log₂(n)次时内层循环耗时

Let’s break this down step by step, starting with the outer loop, then covering common scenarios for the inner loop.

Outer Loop Runtime Analysis #

The loop for(i=1; i<=n; i=i*2) doubles i with each iteration. Here’s how to count its runtimes:

• Starting at i=1, the sequence of i values is 1,2,4,8,16,... until i exceeds n.
• The number of iterations is the smallest integer k where 2^k > n. For example, if n=8, the loop runs 4 times (for i=1,2,4,8), since 2^4=16 is the first power of 2 larger than 8.

In asymptotic complexity terms (the standard way to discuss runtime), this is Θ(log n). We use base-2 logarithm here, but since all logarithms are just constant multiples of each other, we often simplify it to log n in big-O notation.

Inner Loop Runtime: It Depends on the Inner Loop’s Logic #

You already know the outer loop runs log₂(n) times, but the total runtime of the nested structure depends entirely on what the inner loop does per iteration. Here are the most common cases:

• Case 1: Inner loop does constant work (O(1))
  If the inner loop is a single operation (like arithmetic, a print statement, or variable assignment with no nested loops), each outer iteration takes constant time. The total runtime is then O(log n)—just the number of outer iterations multiplied by a fixed constant.

• Case 2: Inner loop runs i times per outer iteration
  Suppose the inner loop is for(j=0; j<i; j++) { /* O(1) work */ }. We need to sum the inner iterations across all outer steps:
  1 + 2 + 4 + 8 + ... + 2^(k-1) where 2^k ≤ n.
  This is a geometric series whose sum equals 2^k - 1, which is at most n-1 (since 2^k ≤n). The total runtime here is O(n).

• Case 3: Inner loop runs logarithmic time relative to i
  If the inner loop itself runs log i times, the sum of iterations becomes log1 + log2 + log4 + ... + log(2^(k-1)). Simplifying this, each term is 0,1,2,...,k-1, so the sum is k(k-1)/2. Since k=log₂(n), this totals to O((log n)²).

The bottom line: You can’t pin down the inner loop’s contribution without knowing what it’s doing—its runtime scales based on the work it performs each outer iteration.

内容的提问来源于stack exchange，提问作者MaG