a********e
发帖数: 53 | 1 这种用dfs的时间复杂度，总是绕不清楚。
code如下，
分析时间复杂度哪种比较对？
一种是dfs一共执行了n！次，每次有n^2, 所以总共是O(n!n^2).
另一种是T(n)= nT(n-1) + n^2, 所以是? 我也不知道了。
////////////////////////////////////
bool PosOK(int col[], int idx){
for ( int i=0; i< idx; i++){
if (col[i]== col[idx] || (idx-i)== abs(col[idx] - col[i] ) )
return false;
}
return true;
}
void dfs2(int col[], int idx, vvs & res, int n){
//when there is a solution
if (idx==n){
string s(n, '.');
vs tmp(n, s);
for (int i=0; i< n; i++)
tmp[i][co... 阅读全帖 |
|
