如何计算的反向跟踪算法

  • Z时代
  • 2024-01-10
  • 分类：问答

都用这个方案，如何计算回溯算法中的时间复杂度的时间复杂度？如何计算的反向跟踪算法

/* 
    Function to print permutations of string This function takes three parameters: 
    1. String 
    2. Starting index of the string 
    3. Ending index of the string. 
*/ 
void swap (char *x, char *y) 
{ 
    char temp; 
    temp = *x; 
    *x = *y; 
    *y = temp; 
} 
void permute(char *a, int i, int n) 
{ 
    int j; 
    if (i == n) 
    printf("%s\n", a); 
    else 
    { 
    for (j = i; j <= n; j++) 
    { 
     swap((a+i), (a+j)); 
     permute(a, i+1, n); 
     swap((a+i), (a+j)); //backtrack 
    } 
    } 
}

回答：

每个permute(a,i,n)导致n-i呼叫permute(a,i+1,n)

因此，当i == 0有n电话，当i == 1有n-1电话......当i == n-1有一个呼叫。

可以从此找到迭代次数的递归公式：
T(1) = 1 [碱];和T(n) = n * T(n-1) [步骤]

导致合计T(n) = n * T(n-1) = n * (n-1) * T(n-2) = .... = n * (n-1) * ... * 1 = n!

EDIT的：[小校正]：由于在for循环的条件是j <= n [和不j < n]，各permute()被实际调用n-i+1倍permute(a,i+1,n) ，从而导致T（N）= (n+1) * T(n-1) [步骤]和T(0) = 1 [碱]，后来导致T(n) = (n+1) * n * ... * 1 = (n+1)!。
但是，它似乎是一个执行错误超过一个功能：\

回答：

一个简单的直觉是，会有n！排列，你必须产生所有这些。因此，你的时间复杂度至少是n！因为你将不得不遍历所有n！以便生成它们全部。因此，时间复杂度是O（n！）。

以上是 如何计算的反向跟踪算法 的全部内容， 来源链接： utcz.com/qa/260292.html

回到顶部