複雜的回溯算法

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)); 
} 

上面的代碼中你所提到的時間複雜度運行。