如何计算回溯算法的时间复杂度？ [英] How to calculate time complexity of backtracking algorithm?
问题描述
如何为这些回溯算法计算时间复杂度，并且它们具有相同的时间复杂度？如果不同怎么办？请详细解释，并感谢您的帮助。
How to calculate time complexity for these backtracking algorithms and do they have same time complexity? If different how? Kindly explain in detail and thanks for the help.
1. Hamiltonian cycle:
bool hamCycleUtil(bool graph[V][V], int path[], int pos) {
/* base case: If all vertices are included in Hamiltonian Cycle */
if (pos == V) {
// And if there is an edge from the last included vertex to the
// first vertex
if ( graph[ path[pos-1] ][ path[0] ] == 1 )
return true;
else
return false;
}
// Try different vertices as a next candidate in Hamiltonian Cycle.
// We don't try for 0 as we included 0 as starting point in in hamCycle()
for (int v = 1; v < V; v++) {
/* Check if this vertex can be added to Hamiltonian Cycle */
if (isSafe(v, graph, path, pos)) {
path[pos] = v;
/* recur to construct rest of the path */
if (hamCycleUtil (graph, path, pos+1) == true)
return true;
/* If adding vertex v doesn't lead to a solution, then remove it */
path[pos] = -1;
}
}
/* If no vertex can be added to Hamiltonian Cycle constructed so far, then return false */
return false;
}
2. Word break:
a. bool wordBreak(string str) {
int size = str.size();
// Base case
if (size == 0)
return true;
// Try all prefixes of lengths from 1 to size
for (int i=1; i<=size; i++) {
// The parameter for dictionaryContains is str.substr(0, i)
// str.substr(0, i) which is prefix (of input string) of
// length 'i'. We first check whether current prefix is in
// dictionary. Then we recursively check for remaining string
// str.substr(i, size-i) which is suffix of length size-i
if (dictionaryContains( str.substr(0, i) ) && wordBreak( str.substr(i, size-i) ))
return true;
}
// If we have tried all prefixes and none of them worked
return false;
}
b. String SegmentString(String input, Set<String> dict) {
if (dict.contains(input)) return input;
int len = input.length();
for (int i = 1; i < len; i++) {
String prefix = input.substring(0, i);
if (dict.contains(prefix)) {
String suffix = input.substring(i, len);
String segSuffix = SegmentString(suffix, dict);
if (segSuffix != null) {
return prefix + " " + segSuffix;
}
}
}
return null;
}
3. N Queens:
bool solveNQUtil(int board[N][N], int col) {
/* base case: If all queens are placed then return true */
if (col >= N)
return true;
/* Consider this column and try placing this queen in all rows one by one */
for (int i = 0; i < N; i++) {
/* Check if queen can be placed on board[i][col] */
if ( isSafe(board, i, col) ) {
/* Place this queen in board[i][col] */
board[i][col] = 1;
/* recur to place rest of the queens */
if ( solveNQUtil(board, col + 1) == true )
return true;
/* If placing queen in board[i][col] doesn't lead to a solution then remove queen from board[i][col] */
board[i][col] = 0; // BACKTRACK
}
}
}
我实际上是有点困惑，至于Word Break（b）的复杂度为O（2 n ），但对于汉密尔顿循环，其复杂度不同，因此打印相同字符串的不同排列也是如此，然后再次求解n个皇后问题。
I am actually confused a bit, as for Word Break(b) the complexity is O(2n) but for Hamiltonian cycle its different and so does for printing different permutations of the same string and then again for solving n queens problem.
推荐答案
简而言之：
In short:
- 汉密尔顿周期：
O（N！）在最坏的情况下 - WordBreak和StringSegment：
O（2 ^ N） - NQueens：
O（N！）
- Hamiltonian cycle :
O(N!)in the worst case - WordBreak and StringSegment :
O(2^N) - NQueens :
O(N!)
注意：对于WordBreak，有一个O（N ^ 2）动态编程解决方案。
Note: For WordBreak there is an O(N^2) dynamic programming solution.
-
在哈密顿循环中，在每个递归调用中，从中选择剩余的顶点之一最坏的情况。在每个递归调用中，分支因子均减小1。在这种情况下，递归可以看作是n个嵌套循环，其中在每个循环中，迭代次数均减小1。因此，时间复杂度由下式给出：
In Hamiltonian cycle, in each recursive call one of the remaining vertices is selected in the worst case. In each recursive call the branch factor decreases by 1. Recursion in this case can be thought of as n nested loops where in each loop the number of iterations decreases by one. Hence the time complexity is given by:
T（N）= N *（T（N-1）+ O（1））
T（N）= N *（N-1）*（N-2）.. = O（N！）
与NQueens类似，每次分支因子减少1或更多但不多，因此的上限O（N！）
Similarly in NQueens, each time the branching factor decreases by 1 or more, but not much, hence the upper bound of O(N!)
对于WordBreak来说，它比较复杂，但是我可以给您一个大概的想法。在WordBreak中，在最坏的情况下，字符串的每个字符都有两个选择，要么是前一个单词的最后一个字母，要么是新单词的第一个字母，因此分支因子为2。 SegmentString T（N）= O（2 ^ N）
For WordBreak it is more complicated but I can give you an approximate idea. In WordBreak each character of the string has two choices in the worst case, either to be the last letter in the previous word, or to be the first letter of a new word, hence the branching factor is 2. Therefore for both WordBreak & SegmentString T(N) = O(2^N)
这篇关于如何计算回溯算法的时间复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
