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][col[i]] = 'Q';
res.push_back(tmp);
}
//try different position for queen in row idx
for (int i=0 ;i < n; i++){
col[idx] = i;
//test if it is ok to put queen at position i
if (PosOK(col, idx) ){
dfs2(col, idx+1, res, n);
}
}
}
vvs PlaceQueen2(int n){
int col[n];
vvs res;
dfs2(col, 0, res, n);
return res;
} | l*****a
发帖数: 14598 | 2 每次n2从哪里来的？
【在 a********e 的大作中提到】
: 这种用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;
| a********e
发帖数: 53 | 3 一个是for loop，还有一个是PosOK这个function |
|
