다음 알고리즘의 런타임 복잡도

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 지금까지 가장 작은 것보다 작은 정수를 찾는 목록을 따라 탐색합니다. 발견하는 경우, check 통화 자체가 재귀 적으로 더

내가 입력

10 9 8 7 6 5 4 3 2 1

처럼 완전히 역순 에있을 때 최악의 경우가있을 거라고 생각 찾을 수

그래서이 알고리즘의 런타임 복잡성은 무엇입니까?

출처

2016-10-16 viru

라고하지,하지만 '긴 서브를 감소'. 그것은 '가장 길게 증가하는 서브 시퀀스'와 유사하며, 위키피디아 전용 페이지의 고전적인 문제점입니다. 여기서 물어보기 전에 이미 그러한 자료를 확인 했습니까? – o9000

런타임 복잡도는 일반적으로 세 가지 수량으로 설명됩니다 : * average *, * best case * 및 * worst case *. 어느 것을 찾으십니까? 당신은 이미 최악의 경우를 지적했다 - 재귀 호출을 합산한다. 가장 좋은 경우는 선형이고, 평균은 더 복잡 할 것이다. – BeyelerStudios

@ o900이 말한 것과 같이, 이것은 확고한 의문입니다. 솔루션의 모양은 도움이되지 않지만 한 가지 제안을하십시오. 전반적으로 문제를 해결하면서 처음에는 시간 복잡성에 대해 생각하지 마십시오. 일단 당신이 확증되고 입증 된 구현을 갖게되면, 그것을 항상 다듬거나 더 나은 솔루션을 식별 할 수 있습니다. –

문제 문이 가장 길게 증가하는 서브 시퀀스 문제와 일치합니다.

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)

출처

2016-10-16 12:27:56 ruhul

다음 알고리즘의 런타임 복잡도

답변

관련 문제