如何计算这些回溯算法的时间复杂度？它们的时间复杂度是否相同？如果不同，那么它们之间有什么区别？请详细解释，并感谢您的帮助。
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
}
}
}
我有些困惑，因为单词拆分的复杂度是O（2n），但汉密尔顿回路、打印相同字符串的不同排列和解决N皇后问题的复杂度都不同。