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

       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)。

Answer 2

这是我对此的看法

编辑： 这适用于基本条件不抛出异常的情况

control 方法有一个循环运行 vertices 次 - 所以它是 O(vertices).
find是一个递归函数，当n到达vertices时停止。（假设 n 从 1 开始）它为 n=1,2,3... 顶点调用 control。

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

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

编辑：

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

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

Time complexity of recursion inside of for loop

java

complexity-theory

big-o

time-complexity