최 장 상승 서브 시퀀스 O (nlogn) 알고리즘
예 를 들 어 시퀀스: {1, 4, 2, 3, 7, 6, 5 7} 의 최 장 상승 서브 시퀀스 는 {1, 2, 3, 6, 7} 이 고 길 이 는 5 입 니 다.
이 문제 의 답 은 O (nlogn) 와 O (n) 입 니 다. 그 전에 저 는 n ^ 2 의 알고리즘 만 알 고 nlogn 의 알고리즘 을 보지 못 했 습 니 다. 인터넷 에서 검색 한 결과 이 알고리즘 에 대한 소개 가 어렵 고 어렵 다 는 것 을 알 게 되 었 습 니 다. 그래서 저 는 이 알고리즘 을 이해 한 후에 블 로 그 를 써 서 이 알고리즘 을 상세 하 게 소개 하여 최대한 쉽게 이해 하도록 하기 로 했 습 니 다.
설명 하기 편리 하도록 가설 서열 은 num 배열 에 저 장 됩 니 다.
이 문제 에 대하 여 우 리 는 곧 간단 한 산법 을 찾 을 수 있 을 것 이다.배열 length 를 정의 합 니 다. lenth [i] 는 i 요소 의 끝 에 표 시 된 최 장 상승 서브 시퀀스 의 길 이 를 표시 합 니 다.다음 과 같은 전환 관 계 를 생각 할 수 있 습 니 다. length [i] = max (length [j]) + 1, 그 중에서 0 < = j < i 및 num [i] > = num [j] 를 프로그램 으로 다음 과 같이 실현 합 니 다.
int cal(const int *num ,int size)
{
int *length ,i ,j ,r ,maxl = 1;
length = (int*)malloc(size<<2);
for(i = 0 ;i < size ;i ++)
{
r = 0;
for(j = 0 ;j < i ;j ++)
if(num[j] <= num[i] && length[j] > r)
r = length[j];
length[i] = r + 1;
maxl = r+1 > maxl ? r+1 : maxl;
}
free(length);
return maxl;
}
상기 알고리즘 의 시간 복잡 도 는 O (n ^ 2) 이 고 공간 복잡 도 는 O (n) 인 데 어떻게 O (nlogn) 의 복잡 도 에서 가장 긴 상승 서브 시퀀스 문 제 를 풀 수 있 습 니까?우 리 는 일반 O (n ^ 2) 의 알고리즘 을 알 고 있 습 니 다. 2 분 의 사상 을 넣 으 면 대부분 O (nlogn) 로 최적화 할 수 있 기 때문에 상기 알고리즘 에서 2 분 을 어떻게 이용 하 느 냐 가 관건 입 니 다.
우 리 는 하나의 배열 minv, minv [i] 를 정의 하여 길이 가 i 인 하위 서열 에서 가장 큰 요소 의 값 을 나타 낸다. 이 배열 은 반드시 다음 과 같은 성질 이 있 을 것 이다. 임 의 i > j 에 대해 반드시 minv [i] > = minv [j] 가 있 을 것 이다. 즉, minv 는 반드시 오름차 가 있 을 것 이다.증명: 길이 가 i 인 상승 서브 시퀀스 의 마지막 요소 인 minv [i] 는 반드시 이 시퀀스 의 임의의 요소 보다 클 것 이다. i > j 이기 때문에 반드시 minv [i] > minv [j] 가 있 을 것 이다.
제목 의 시퀀스 에 대응 하 는 minv 배열 은 {1, 2, 3, 5, 7} 입 니 다.만약 지금 원 서열 의 끝 에 10 을 더 하려 면 minv 배열 은 {1, 2, 3, 5, 7, 10} 으로 변 한다.상기 과정 에서 알 수 있 듯 이 수 x 를 추가 한 후에 minv 배열 을 구 하 는 것 은 원래 의 minv 배열 에서 위치 가 가장 뒤쪽 이 고 값 이 x 와 같은 요 소 를 찾 는 것 이다. 이 요소 의 아래 표 시 를 k 로 설정 하면 x 와 길이 가 k 인 하위 서열 은 길이 가 k + 1 인 하위 서열 을 구성 한 다음 에 minv [k + 1] = min (x, min [k + 1]) 을 업데이트 하면 된다.minv 는 질서 가 있 기 때문에 위의 과정 은 2 분 으로 찾 을 수 있 고 시간 복잡 도 를 O (nlogn) 로 낮 출 수 있 으 며 프로그램 으로 다음 과 같이 실현 할 수 있 습 니 다.
int cal(const int *num ,int size)
{
int i ,len=1 ,*minv;
int left ,right ,mid ,pos;
minv = (int*)malloc(size<<2);
minv[0] = num[0];
for(i = 1 ; i < size ;i ++)
{
left = 0 ;
right = len - 1;
while(left<=right)
{
mid = (left+right)>>1;
if(minv[mid] > num[i])
right = mid - 1;
else
left = mid + 1;
}
pos = right;
if(pos == len-1)
{
minv[len++] = num[i];
}
else
{
minv[pos+1] = num[i] < minv[pos+1] ? num[i] : minv[pos+1];
}
}
free(minv);
return len;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.