以下のアルゴリズムの実行時の複雑さ

Question

最大10,000個の整数（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, 999999)); 
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+1, nmatches+1, sequence[i]); 
18    if (better > best) best = better; 
19   } 
20  } 
21  return best; 
22 } 

行1-9と11-12は、間違いなく定型文です。彼らはいくつかの標準変数を設定し、入力を取得します。魔法は行10にあり、再帰ルーチンはcheckです。 checkルーチンは、より小さい整数、これまでの最長シーケンスの長さ、これまでの最小の整数の検索をどこから始めるべきかを知っています。余分なコールを犠牲にして、スタートが適切な範囲内になくなると自動的に終了します。ルーチンは簡単です。これは、これまでの最小値より小さい整数を探すリストに沿って移動します。見つかった場合、checkコール自体を再帰的にiが入力

ように完全に逆の順序 にあるときに、最悪の場合になるであろうと思う

詳細を見つけるために

このアルゴリズムの実行時の複雑さは何ですか、私はそれを見つけるのが難しいです...

Answer 1

あなたの問題文は、最長増加サブシーケンス問題と一致します。

あなたは何もしていませんmemoization最悪の場合、実装の複雑さはO(n^n)です。各再帰呼び出しでは(n-1)再帰呼び出しなどが生成されるためです。木を描き、葉の数を確認してみてください。 `

  n 
     /\ \.......... 
    / \   \ 
    (n-1) (n-1) ...... (n-1) 
/\ 
(n-2) (n-2)........(n-2) 
` 

このリンクLongest_increasing_subsequenceをチェックしてください。効率的な実施のためにも

とより多くの知識、この点を確認してください。Dynamic Programming | Set 3 (Longest Increasing Subsequence)