嵌套循环函数时间复杂度O(n^5)的数学证明请求

Hey there, let's break down the time complexity step by step to understand why the problem states it's O(n⁵) (focusing on the worst-case upper bound, which is what the question refers to).

First, here's your code for easy reference:

void function(int n) { 
    int count = 0; 
    for (int i=0; i<n; i++) { 
        for (int j=i; j< i*i; j++) { 
            if (j%i == 0) { 
                for (int k=0; k<j; k++) 
                    printf("*"); 
            } 
        } 
    } 
}

Step 1: Skip Non-Contributing Iterations #

Let's start by eliminating cases where no work gets done:

• When i=0: The inner loop condition j < 0 is false, so nothing runs.
• When i=1: The inner loop condition j < 1 (with j=1) is false, so nothing runs.
  We only need to analyze i >= 2 since these are the values where the inner loops actually execute.

Step 2: Count Middle Loop Iterations #

For each i >= 2, the middle loop runs from j=i to j = i² - 1. The number of iterations here is roughly i² (since i² - i ≈ i² for large values of i).

Step 3: Worst-Case Assumption for the if Check #

In worst-case time complexity analysis, we calculate the upper bound of runtime—meaning we assume the if (j%i == 0) condition is always true (even though this isn't actually possible for all j values). This gives us the maximum possible runtime scenario.

Step 4: Analyze the Innermost printf Loop #

For each j, the innermost loop runs j times (since k goes from 0 to j-1). The largest value of j for a given i is roughly i², so each innermost loop runs up to O(i²) times.

Step 5: Sum Up the Total Work #

For each i, the total work done is the number of middle loop iterations multiplied by the work per iteration:

• Work per i: O(i²) * O(i²) = O(i⁴)

Now we sum this work over all valid i values (from 2 to n-1):
$$\sum_{i=2}^{n-1} O(i^4)$$

The sum of the 4th powers of integers up to n is a well-known formula dominated by the n⁵ term (the closed-form expression includes an n⁵ component). This makes the total worst-case runtime upper bound O(n⁵).

Quick Note on Actual vs. Worst-Case #

If we calculated the actual number of printf calls (only when j is a multiple of i), we'd get a tighter bound of O(n⁴). But the problem asks for the worst-case runtime upper bound, which is O(n⁵).

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