内层循环依赖外层循环的伪代码Big-O-Notation复杂度计算咨询

Great question—let's break this down properly, since your initial conclusion about the Big-O is correct, but the intermediate summation step had a small mistake (easy to make when dealing with nested loops where the inner depends on the outer index!).

First, let's confirm the inner loop iteration count per outer step:
For each outer loop iteration i (from 1 to n), the inner loop runs from j=3 to j=3i +n. The number of operations here is indeed (3i +n) - 3 + 1 = 3i +n -2 (we add 1 because both endpoints are inclusive). That part of your reasoning was spot-on.

Where things went off track was calculating the total operations: you can't just multiply n by (3i +n -2) because i changes every outer loop iteration. Instead, we need to sum the inner loop counts across all values of i from 1 to n:

Total Operations = Σ (from i=1 to n) [3i + n - 2]

Let's split this sum into three separate parts to compute it easily:

• Σ(3i) = 3 * Σ(i) from 1 to n
• Σ(n) = n * n (since we're adding n exactly n times)
• Σ(-2) = -2 * n (adding -2 exactly n times)

We know that Σ(i) from 1 to n is n(n+1)/2, so substituting that in:

Total Operations = 3*(n(n+1)/2) + n² - 2n

Now expand and simplify:

1. Expand the first term: (3n² + 3n)/2
2. Combine all terms over a common denominator:

   (3n² +3n + 2n² -4n)/2 = (5n² -n)/2
   

When converting to Big-O notation, we ignore constant factors and lower-order terms. Here, the highest-order term is 5n²/2, so we drop the 5/2 constant and the -n lower-order term. This leaves us with O(n²), which matches your final conclusion.

So your end result was right—you just took a misstep in how you calculated the total operations. The key here is remembering to sum the inner loop counts instead of multiplying by n when the inner loop's range depends on the outer index.

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