该怎么推导下面算法时间复杂度O(N!*N)的*N？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

该怎么推导下面算法时间复杂度O(N!*N)的*N？

该怎么推导下面算法时间复杂度O(N!*N)的*N？# Programming - 葵花宝典

h*72018-09-19 07:09

1 楼

求助～去年年底申的chase美联航的信用卡，给了7万迈，已经换机票了，现在关，机票
会被取消吗？

n*w2018-09-19 07:09

2 楼

下面是N-Queen的一个native解法。该怎么推导下面算法时间复杂度O(N!*N)的*N？N!容
易看出来。这个 *N 应该是和这行if (!Valid(s, row, i)) continue;有关？
static void DFS(int[] s, int row, List> allSolutions)
{
var N = s.Length;
if (row == N)
{
var solution = s.Select(x => { var a = new bool[N]; a[x] =
true; return a; }).ToList();
allSolutions.Add(solution);
PrintSolution(solution);
return;
};
for (var i = 0; i < N; i++)
{
if (!Valid(s, row, i)) continue;
s[row] = i;
// Console.WriteLine(s.Aggregate($"{row}-", (a, n)=> $"{a} {
(n==-1?".":n.ToString())}"));
DFS(s, row + 1, allSolutions);
}
}
static private bool Valid(int[] s, int row, int col)
{
for (var i = 0; i < row; i++)
{
if (s[i] == col) return false;
if (Math.Abs(row - i) == Math.Abs(col - s[i])) return false;
}
return true;
}
static List> Solve(int n)
{
var allSolutions = new List>();
var s = new int[n];
Array.Fill(s, -1);
DFS(s, 0, allSolutions);
return allSolutions;
}

b*82018-09-19 07:09

3 楼

d*a2018-09-19 07:09

4 楼

对。Valid过程的执行代价是O(N)。DFS一共被调用了N!次，每次除递归调用之外的执行
代价是O(N)，所以总的代价是O(N!*N)。

【在 n*w 的大作中提到】

: 下面是N-Queen的一个native解法。该怎么推导下面算法时间复杂度O(N!*N)的*N？N!容
: 易看出来。这个 *N 应该是和这行if (!Valid(s, row, i)) continue;有关？
: static void DFS(int[] s, int row, List> allSolutions)
: {
: var N = s.Length;
: if (row == N)
: {
: var solution = s.Select(x => { var a = new bool[N]; a[x] =
: true; return a; }).ToList();
: allSolutions.Add(solution);

h*72018-09-19 07:09

5 楼

谢谢~

【在 b********8 的大作中提到】

: no

n*w2018-09-19 07:09

6 楼

看起来像是 O(N!+N) = O(N!)?
而且valid的执行代价应该小于O(N)。valid的调用参数先是很小。等处理的row多了的
话又很容易提前return false？
不过试了一下4-queen，loop的次数确实大于4！。

【在 d***a 的大作中提到】

: 对。Valid过程的执行代价是O(N)。DFS一共被调用了N!次，每次除递归调用之外的执行
: 代价是O(N)，所以总的代价是O(N!*N)。