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

기능을 호출하는 매개 변수의 종류를 살펴보십시오. 첫 번째는 세 번째 매개 변수를 결정합니다 (btw는 세 번째 매개 변수가 필요함을 의미 함). 첫 번째 범위는 0과 n 사이입니다. 두 번째 것은 첫 번째 것보다 작습니다. 즉, 최대 n^2 개의 다른 함수 호출이 있음을 의미합니다.

이제는 동일한 매개 변수를 사용하여 함수를 몇 번이나 호출했는지 묻습니다. 그리고 대답은 간단합니다. 실제로 모든 단일 감소 서브 시퀀스를 생성합니다. 이것은 시퀀스 N, N-1, N-2, ...에 대해 2^N 시퀀스를 생성한다는 것을 의미합니다. 꽤 가난하고, 맞다. (내가 당신에게 준 시퀀스를 실험하고 싶다면)?

그러나 이미 읽었어야하는 메모 기법을 사용하면 복잡성을 N^3으로 향상시킬 수 있습니다 (함수를 호출 할 때마다 n 회까지의 작업, 다른 호출은 N^2이며 메모 작성을 통해 다른 전화로 한 번만 지불하는 것).