DP 최적화를 위한 단일 대기열 기능(오늘 점심)
4342 단어 ACM_단조 대열
단조로운 대기열은 이해하기 쉽다. 바로 양방향 대기열이다. 대기열의 첫 번째 대기열은 삭제 작업을 허용하고 대기열의 끝은 추가 작업을 한다. 전체 대기열의 엄격한 단조성을 유지한다. 즉, 대기열에 같은 요소가 존재하지 않는다(이렇게 하면 시간 상수는 조금 작다).
그렇다면 단조로운 대기열로 최적화된 DP는 어떤 성격을 지니고 있을까?
만약 우리가 아래의 DP 전이 방정식을 가지고 있다면:
f[i] = min( f[j] ) + a[i]
그러면 j가 하나의 조건을 만족시킬 때: Low[i]<=j<=Up[i], 이곳의 Low와 Up은 i에 관한 단조로운 함수이고 단조로운 증가이다. 왜?고전적인 단조로운 팀을 연결하여 문제에 넣는다. 슬라이딩 윈도는 생각해 보면 알 수 있다. 내가 다음 Low[i]를 사용할 때 Low[i]는 Low[i-1]보다 커야 한다. 왜냐하면 팀의 첫 번째는 대열을 나가는 조작과 관련이 있기 때문이다. 그리고 팀의 끝의 원소 상계: Up도 단조롭게 증가하는 성질을 가져야 한다. 왜냐하면 대열의 원소를 다시 사용할 때 원소를 추가하는 조작과 관련이 있기 때문이다.아직도 잘 모르겠다면 슬라이딩 윈도에 연락해서 이 단조로운 대기열에서 삽입을 삭제하는 과정을 자세히 생각해 보면 된다.그래, 납득했어.
그렇다면 단조로운 대열은 도대체 어느 정도까지 최적화될 수 있을까?다음 실험을 살펴보겠습니다.
【실험방정식】:
f[i] = min ( f[j] ) + a[i] ( 1<= j <= i-1 )
【실험과정】:
나는 테스트 데이터를 하나 만들었는데, 크지 않아, 마침 10^5개의 수가 있다.전통적인 o(n^2)의 알고리즘으로 시간 초과를 확정했다. 이 전이 방정식을 보면 우리는 단조로운 대기열을 사용하지 않고 o(n)의 복잡도를 최적화할 수 있다. 바로 1-i의 최소치를 기록하는 것이다. 민이 f[i]를 계산할 때마다 민+a[i]를 사용하면 된다.
그러면 이 문제는 모두 세 개의 프로그램을 쓸 수 있는데 시간의 복잡도는 각각이다.
전통적인 이중 순환 판정: o(n^2)
최소값으로 최적화: o (n)
단조로운 대기열로 최적화: 알 수 없음 (이것이 바로 이 실험에서 연구하고자 하는 내용)
실험 절차는 다음과 같습니다.
1. 전통적인 이중 순환 판정:
#include
#include
#include
#include
#include
#include
#define INF 0x7fffffff
using namespace std;
int main()
{
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
int n,a[100005],f[100005];
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
f[1]=a[1];
for(int i=2;i<=n;i++)
{
int Min=INF;
for(int j=1;jf[j]) Min=f[j];
f[i]=Min+a[i];
}
for(int i=1;i<=n;i++)
{
printf("%d",f[i]);
if(i==n) printf("
");
else printf(" ");
}
return 0;
}
최소값으로 최적화:
#include
#include
#include
#include
#include
#include
#define INF 0x7fffffff
using namespace std;
int main()
{
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
int n,a[100005],f[100005];
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
f[1]=a[1];
int Min=f[1];
for(int i=2;i<=n;i++)
{
f[i]=Min+a[i];
if(f[i] 단일 큐로 최적화:
#include
#include
#include
#include
#include
#include
#define INF 0x7fffffff
using namespace std;
int main()
{
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
int n,a[100005],f[100005];
int q[200000],head,tail;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
f[1]=a[1];
tail=1; head=0; q[1]=1;
for(int i=2;i<=n;i++)
{
f[i]=f[q[1]]+a[i];
//printf("f[q[1]]=%d
",f[q[1]]);
//printf("f[%d]=%d
",i,f[i]);
while(f[i]<=f[q[tail]] && 1<=tail) tail--;
q[++tail]=i;
}
for(int i=1;i<=n;i++)
{
printf("%d",f[i]);
if(i==n) printf("
");
else printf(" ");
}
return 0;
}
프로그램이 있으면 우리는 실험을 할 수 있다.
나는 먼저 10^4의 데이터 규모를 사용하여 이 세 프로그램을 테스트했다. 다음은 그들이 달리는 시간을 살펴보자.
위의 데이터 결과를 통해 알 수 있듯이 붉은 과일의 이중 순환을 사용하면 소모되는 시간은 o(n) 알고리즘의 60배에 달한다. 그러나 단조로운 대기열 최적화 방법을 사용할 때 시간은 내가 예상한'붉은 과일의 o(n^2)와 차이가 많지 않다'는 것과 큰 차이가 있다. 뜻밖에도 o(n)와 거의 같다!그래서 사악함을 믿지 않는 나는 또 한 조의 데이터를 시험해 보았다. 이로써 나는 데이터 규모를 10^5급으로 늘렸다. 다음은 실험 결과이다.
내 생각에 이 지경에 이르렀을 때 단조로운 대열의 시간 복잡도는 우리가 의심할 필요가 없다. 이것은 일중순환을 없애고 토치카에 나무가 있는 것과 같다!!
그래서 앞으로 단조로운 대기열을 쓸 수 있으면 최대한 단조로운 대기열을 쓰도록 하겠습니다.
좋은 웹페이지 즐겨찾기
