for 循环内递归的时间复杂度

Question

你能帮我解决这段代码的时间复杂度吗？我认为它是 3^n，但我是新手，所以我可能是错的。

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;
    }

任何帮助不胜感激！

编辑：我想我误解了一些事情，复杂性是n。

Answer 1

这是我

对此的看法

编辑：当基本条件不引发异常时，这适用

1. control方法有一个运行vertices次的循环 - 所以它是O(vertices) .

2. find是一个递归函数，当n达到vertices时停止。(假设n从 1 开始(它调用 control 对于 n=1,2,3...顶点。

从循环调用 find 3 次。每个递归调用都涉及这一点，因此这使得它呈指数级 - O(3^vertices) 。

所以，最后，它是O(3^vertices) * O(vertices)这是O(3^vertices)

编辑：

因为你有throw new Exception("Solution found");，一旦n到达顶点，它就会爆炸。所以它以这种方式O(vertices^2)。

Answer 2

       n
      /|
     / |  
    /  |  
   /   |   
(n+1) (n+1)(n+1) --> control(vertex)-> O(Vertex)
 /|
/ |  . . . .   . .

因此，似乎有总共3^1+ 3^2+...+3^vertex节点，并且在每个节点上您正在每个节点上执行O(n)操作。所以复杂性是 O((3^1+ 3^2+...+3^n) * n) = O((1-3^n)/2)*n)最终O((3^vertices)*vertices) .