최 장 상승 서브 시퀀스 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;
}