递归算法复杂度计算：含循环与两次递归调用的func3分析

Great question! Let's break down how to analyze the time complexity of your func3 function step by step—starting with a critical syntax detail that’s easy to overlook in the original code.

First, let’s restate the code clearly (with Java syntax clarified):

func3(int n) { 
    // Loop runs (n-1) times, printing a "*" each iteration
    for (int i = 1; i < n; i++) {
        System.out.println("*");
    }

    // Base case: print once and return
    if (n <= 1) {
        System.out.println("*");
        return;
    }

    // IMPORTANT: No curly braces after the if, so only func3(n-1) is conditional
    if (n % 2 != 0) {
        func3(n - 1);
    }
    // This recursive call runs for ALL n > 1, even when n is even
    func3(n / 2);
    return;
}

Step 1: Define the Time Complexity Function #

Let T(n) represent the total number of println operations executed by func3(n)—since each print is a constant-time basic operation, we can use this count to measure time complexity.

Step 2: Establish Recurrence Relations #

We split into cases based on the value of n:

Base Case

When n ≤ 1, we only execute one print statement:

T(n) = 1

Recursive Cases (n > 1)

For any n > 1:

1. The loop contributes n-1 print operations.
2. We then handle recursive calls based on whether n is odd or even:
   • If n is odd: We run both func3(n-1) and func3(n//2) (where // denotes integer division). The recurrence becomes:

     T(n) = (n-1) + T(n-1) + T(n//2)
     

   • If n is even: We only run func3(n//2) (the conditional func3(n-1) is skipped). The recurrence becomes:

     T(n) = (n-1) + T(n//2)
     

Step 3: Analyze the Recurrence Relations #

To find the asymptotic time complexity, we focus on the worst-case scenario (since even cases are simpler and grow slower than odd cases):

Worst-Case: n is Odd

When n is odd, n-1 is even, so we combine the two recurrence rules. Let’s use induction and recursive tree analysis to find the bounds:

• Upper Bound: Assume T(m) ≤ C·m·log m for all m < n (where C is a constant). For odd n:

  T(n) = (n-1) + T(n-1) + T(n//2)
       ≤ n + C·(n-1)·log(n-1) + C·(n//2)·log(n//2)
       ≤ n + C·n·log n + C·(n/2)·log n
  

  For sufficiently large n and C ≥ 2, the n term is negligible compared to C·n·log n, so T(n) = O(n log n).

• Lower Bound: Consider values of n that are one less than a power of two (e.g., 3=2²-1, 7=2³-1, 15=2⁴-1). For these n, the recurrence simplifies to a form that expands to T(n) = Ω(n log n) (you can verify this by expanding the recurrence for n=2ᵏ-1, which yields a linear term multiplied by log n).

Even-Case Behavior

For even n, the recurrence T(n) = (n-1) + T(n//2) expands to a sum of linear terms:

T(2ᵏ) = (2ᵏ-1) + (2ᵏ⁻¹-1) + ... + (2¹-1) + T(1)
= 2(2ᵏ - 1) - k + 1 = 2n - log₂n - 1

This is O(n), which is slower-growing than the worst-case odd scenario.

Final Conclusion #

Since the worst-case time complexity dominates, the overall time complexity of func3(n) is Θ(n log n).

Key Takeaway for Mixed Loop/Recursion Analysis #

When dealing with functions that have both loops and recursive calls:

• First calculate the time cost of the non-recursive parts (like the n-1 loop here) for a single call.
• Write a recurrence relation that adds this non-recursive cost to the time costs of all recursive calls.
• Analyze the recurrence relation (using induction, recursive trees, or master theorem if applicable) to find asymptotic bounds.

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