这个算法用于解决Sudoku的时间复杂度是多少？
数独求解器
编写一个程序，通过填充空单元格来解决数独谜题。
空单元格由字符'。'表示。
你可能会认为只会有一个独特的解决方案 。
我个人认为，
时间复杂度= O（（n ^ 2）！），n是电路板的行数（cols）。
C ++
class Solution {
public:
void solveSudoku(vector<vector<char> > &board) {
// Input validation.
if (board.size() == 0 ||
board.size() != board[0].size() ||
board.size() % 3 != 0) return;
helper(board);
}
bool helper(vector<vector<char>>& board) {
// Base case.
// ... ...
for (int row = 0; row < board.size(); row ++) {
for (int col = 0; col < board[0].size(); col ++) {
if (board[row][col] != '.') continue;
for (char num = '1'; num <= '9'; num ++) {
if (isValid(board, num, row, col)) {
// Have a try.
board[row][col] = num;
// Do recursion.
if (helper(board)) return true;;
// Roll back.
board[row][col] = '.';
}
}
// Can not find a suitable number[1-9].
return false;
}
}
return true;
}
bool isValid(const vector<vector<char>>& board, char num, int row, int col) {
// Check row.
for (int tmp_col = 0; tmp_col < board[0].size(); tmp_col ++) {
if (board[row][tmp_col] == num) return false;
}
// Check col.
for (int tmp_row = 0; tmp_row < board.size(); tmp_row ++) {
if (board[tmp_row][col] == num) return false;
}
// Check sub square.
int start_row = (row / 3) * 3;
int start_col = (col / 3) * 3;
for (int row = start_row; row < start_row + 3; row ++) {
for (int col = start_col; col < start_col + 3; col ++) {
if (board[row][col] == num) return false;
}
}
return true;
}
};
你认为O（（n ^ 2）！）的原因是什么？ 既然这是一个带回溯的经典递归，我会在没有深入分析问题的情况下认为它是O（n ^ n）。 尝试制作一个计数器，每次函数递归调用时递增。 然后看算法结束时是否接近387 420 489（我的猜测）或579 712 600 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000（您的猜测）。
如果你想要更复杂的解释，我很乐意给出一个。
编辑：在仔细思考详细解释的同时，我注意到我错了数字，他们实际上应该更高一些。
许多递归搜索可以建模为树。 在Sodoku中，每次尝试新场时都有9种可能性。 最大限度地，你必须把解决方案放到所有81个领域。 在这一点上，它可以帮助绘制它，以便查看所得到的搜索空间是在每个层的每个节点处深度为81和分支因子为9的树，并且每个树叶都是可能的解决方案。 给定这些数字，搜索空间是9 ^ 81。
由于您在尝试81次后并没有检查解决方案是否正确，但在每次尝试后，实际搜索空间都小得多。 我不知道如何把它变成数字，也许每当你设置n次尝试时，分支因子就会减少1，这是一个粗略的估计。 但是，如果有任何有k个预设数字的Sodoku，你可以100％肯定地说，你最多需要n ^（n2-k）次尝试。
这有道理吗？
链接地址: http://www.djcxy.com/p/96165.html上一篇: What's time complexity of this algorithm for solving Sudoku?