search

liuchuo / PAT

🍭 浙江大学PAT题解(C/C++/Java/Python) - 努力成为萌萌的程序媛～
3.37k stars 824 forks source link

PAT-甲级 1013题，我觉得这个用dfs()的复杂度是O(n^4) #5

Closed chengshuyi closed 6 years ago

chengshuyi commented 7 years ago

我觉得这里的dfs()的时间复杂度是O(n^2)

 for(int i = 0; i < k; i++) {                                        //Kmax=n
        fill(visit, visit + 1010, false);
        scanf("%d", &a);
        int cnt = 0;
        visit[a] = true;
        for(int j = 1; j <= n; j++) {                             //Jmax=n
            if(visit[j] == false) {                                
                dfs(j);                                                     //dfs是O(n^2)
                cnt++;
            }
        }
        printf("%d\n", cnt - 1);
    }

你觉得呢？

liuchuo commented 7 years ago

你这么厉害，说什么都对～(^__^) 嘻嘻…… //大神莫嘲笑，我不太懂时间复杂度的计算。。