循环内递归的时间复杂度分析求助：判断代码是否为3^n

Hey there! Let's break down the time complexity of your backtracking graph coloring code—you're on the right track with the exponential part, but we need to account for a key detail you might have overlooked.

First, let's recap your code for clarity:

public void find(int n) throws Exception { 
    if (n == vertices){ 
        throw new Exception("Solution found"); 
    } 
    for (int r = 1; r <= 3; r++) { 
        if (control(n, r)) { 
            color[n] = r; 
            find(n + 1); 
            color[n] = 0; 
        } 
    } 
} 
public boolean control(int n, int r) { 
    for (int i = 0; i < vertices; i++){ 
        if (graph[n][i] == 1 && r == color[i]){ 
            return false; 
        } 
    } 
    return true; 
}

Recursive Structure of find() #

Your find() function is a classic backtracking approach for 3-coloring a graph. In the worst-case scenario (e.g., a graph with no edges, so every color choice is valid), each vertex has 3 possible color options that will trigger a recursive call to the next vertex.

This forms a recursive tree where each level corresponds to a vertex, and each node has up to 3 children. The total number of recursive calls here is asymptotically O(3^v), where v is the number of vertices (vertices in your code). Your initial intuition about the 3^n part is spot-on for this recursive call count!

The Overhead of control() #

Where your estimate is incomplete is the cost of the control() function. Every time you check if a color is valid for vertex n, you loop through all v vertices to check for adjacent conflicts. That means each call to control() takes O(v) time.

Since every recursive call to find() triggers at least one call to control(), we have to multiply the number of recursive calls by the cost of each validity check.

Final Time Complexity #

Combining these two factors, the total time complexity of your code is O(v * 3^v).

A quick side note: In practice, if your graph has many edges, most color choices will be invalid early, so the actual number of recursive calls will be lower than 3^v. But time complexity analysis always focuses on the worst-case scenario, which is the edge-free graph where every color is allowed.

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