小编Rah*_*hna的帖子

我必须使用回溯找出图着色问题的时间复杂度。我发现它是 O(n*m^n) 的地方，其中 n=无顶点，m=颜色数。

假设我的代码如下，如何找到时间复杂度？

bool isSafe (int v, bool graph[V][V], int color[], int c)
{
    for (int i = 0; i < V; i++)
        if (graph[v][i] && c == color[i])
            return false;
    return true;
}

bool graphColoringUtil(bool graph[V][V], int m, int color[], int v)
{
    if (v == V)
        return true;

    for (int c = 1; c <= m; c++)
    {
        if (isSafe(v, graph, color, c))
        {
           color[v] = c;

           if (graphColoringUtil (graph, m, color, v+1) == true)
             return …