Big-O算法分析

Question

我會說這不是一個家庭作業問題。它只是一個在線教程資源，用於從USACO網站學習動態編程概念。 在資源中，給出瞭如下問題。

問題： 多達10000個整數的後綴（0 <整數< 100,000），最大遞減子序列是多少？

體面遞歸方法給予

1 #include <stdio.h>  
2 long n, sequence[10000]; 
3 main() { 
4  FILE *in, *out;      
5  int i;        
6  in = fopen ("input.txt", "r");  
7  out = fopen ("output.txt", "w"); 
8  fscanf(in, "%ld", &n);    
9  for (i = 0; i < n; i++) fscanf(in, "%ld", &sequence[i]); 
10  fprintf (out, "%d\n", check (0, 0, 99999)); 
11  exit (0); 
12 } 


13 check (start, nmatches, smallest) { 
14  int better, i, best=nmatches; 
15  for (i = start; i < n; i++) { 
16   if (sequence[i] < smallest) { 
17    better = check (i, nmatches+1, sequence[i]); 
18    if (better > best) best = better; 
19   } 
20  } 
21  return best; 
22 } 

夥計們，我不擅長的算法分析。請您在最壞的情況下儘可能嚴格地告訴我這個遞歸枚舉解決方案的Big-O符號是什麼。我個人的想法是O（N^N），但我沒有信心。因爲在N < = 100下運行時仍然可以接受。一定有什麼問題。請幫幫我。謝謝。

在USACO網站中，它給出了O（n^2）中的動態規劃方法，如下所示。

1 #include <stdio.h> 
2 #define MAXN 10000 
3 main() { 
4  long num[MAXN], bestsofar[MAXN]; 
5  FILE *in, *out; 
6  long n, i, j, longest = 0; 
7  in = fopen ("input.txt", "r"); 
8  out = fopen ("output.txt", "w"); 
9  fscanf(in, "%ld", &n); 
10  for (i = 0; i < n; i++) fscanf(in, "%ld", &num[i]); 
11  bestsofar[n-1] = 1; 
12  for (i = n-1-1; i >= 0; i--) { 
13   bestsofar[i] = 1; 
14   for (j = i+1; j < n; j++) { 
15    if (num[j] < num[i] && bestsofar[j] >= bestsofar[i]) { 
16     bestsofar[i] = bestsofar[j] + 1; 
17     if (bestsofar[i] > longest) longest = bestsofar[i]; 
18    } 
19   } 
20  } 
21  fprintf(out, "bestsofar is %d\n", longest); 
22  exit(0); 
23 } 

Answer 1

只要看看你調用的函數是什麼樣的參數。第一個決定第三個（這意味着你需要第三個參數）。第一個範圍在0和n之間。第二個比第一個小。這意味着您最多有n^2個不同的函數調用。

現在問題出現了多少次你用相同的參數調用函數。答案很簡單：你實際上會生成每一個遞減的事件。這意味着對於序列N，N-1，N-2 ......，您將生成2^N個序列。很差，對（如果你想試試我給你的序列）？

但是，如果您使用memoization技術，您應該已經閱讀過，您可以將複雜度提高到N^3（每次調用函數時最多n次操作，不同的調用次數爲N^2，memoization可以讓您只爲一次不同的通話付費）。