复杂的回溯算法

Question

我试图用回溯来解决这个问题，但我不确定算法的复杂性（如果算法是正确的）以及什么是复杂度更高的算法。

鉴于2个的正整数n和m，我们把合法整数的序列，如果：

• 的序列的长度为n
• 序列中的元素是1且m
• 之间在位置i的元素的序列的，1 <我< = n时，是元件的位置中的除数I-1

计数法定序列的数目。预计该算法的复杂度为O（平方米+纳米）

这是我在C算法：

// n length of the sequence 
// m maximum valid number 
// l number of remaining positions in the sequence 
// p previous number in the sequence 

int legal(int n, int m, int l, int p) { 
    if (l == 0) 
     return 1; 
    int q=0; 
    for (int i=1; i <= m;i++) { 
     if (p%i == 0 || l == n) 
      q += legal(n,m,l-1,i); 
    } 
    return q; 
} 

int main() { 
    int n, m; 
    scanf("%d", &n); 
    scanf("%d", &m);  
    printf("%d\n", legal(n,m,n,0)); 
} 

我觉得我的算法的复杂度为O（NMS（N））与S（N） =合法序列号

Answer 1

您的程序运行在问题的解决方案空间中是正确的。对于这种类型的问题，您的解决方案对于大型输入而言是次优的（比如n = m = 100）。这是因为解决方案空间相对于m和n呈指数增长。下面是一个使用memoization以避免重新计算的解决方案：

#include <cstdio> 

#define LIMIT 101 
#define DIRTY -1 


long long cache[LIMIT][LIMIT]; 

void clear_cache() { 
    for (int i = 0; i < LIMIT; i++) { 
    for (int j = 0; j < LIMIT; j++) { 
     // marked all entries in cache as dirty 
     cache[i][j] = DIRTY; 
    } 
    } 
} 

long long legal_seqs(int curr_len, int prev_num, int seq_len, int max_num) { 
    // base case 
    if (curr_len == seq_len) return 1; 

    // if we haven't seen this sub-problem, compute it! 
    // this is called memoization 
    if (cache[curr_len][prev_num] == DIRTY) { 
    long long ways = 0; 
    // get all multiples of prev_num 
    for (int next_num = 1; next_num <= max_num; next_num++) { 
     if (prev_num % next_num == 0) { 
     ways += legal_seqs(curr_len + 1, next_num, seq_len, max_num); 
     } 
    } 
    cache[curr_len][prev_num] = ways; 
    } 
    return cache[curr_len][prev_num]; 
} 

int main() { 
    int n, m; 
    scanf("%d%d", &n, &m); 
    clear_cache(); 
    printf("%lld\n", legal_seqs(0, 0, n, m)); 
} 

上面的代码中你所提到的时间复杂度运行。