먼저 모든 미생물의 번호를 의 사전순으로 정렬한 순열 을 구한다. 어떤 연구 표본을 고르더라도 성장 계수에 따른 순서는 이 순열의 부분 수열이다.
일차 를 고정하고, 순열의 각 위치에 쌍 를 놓자. 두 쌍은 첫 번째 값이 작은 쪽을 먼저 비교하고, 첫 번째 값이 같으면 두 번째 값이 작은 쪽을 먼저 비교한다. 고른 미생물들의 개체 수 순서까지 같으려면, 고른 위치들의 가 이 비교에 따라 엄격히 증가해야 한다. 따라서 일차에 고를 수 있는 최대 종류 수는 이 쌍들의 최장 증가 부분 수열 길이이다. 개체 수만 비교하면 동률일 때 번호로 정렬한다는 조건을 놓치므로 반드시 번호도 함께 비교한다.
최장 증가 부분 수열은 길이별로 가능한 마지막 쌍의 최솟값을 유지하는 방법으로 구한다. 각 쌍을 차례로 보면서, 마지막 쌍들의 배열에서 현재 쌍 이상인 첫 위치를 이분 탐색해 값을 교체한다. 그런 위치가 없다면 뒤에 추가한다. 이 판정에는 시간이 걸린다.
어느 날 조건을 만족한 표본은 그 이후에도 조건을 만족한다. 따라서 최장 증가 부분 수열의 길이가 이상인지 판정하는 결과는 일차가 증가하면서 거짓에서 참으로만 바뀐다. 라고 하자. 일차에 조건을 만족하면 바로 을 출력한다. 그렇지 않고 일차에도 길이가 보다 작다면 을 출력한다. 나머지 경우에는 에서 조건을 처음 만족하는 일차를 이분 탐색한다.
처음 정렬하는 데 시간이 걸리고, 판정을 번 수행하므로 전체 시간 복잡도는 , 공간 복잡도는 이다.
증명
성장 계수 정렬에서 앞에 오는 미생물 와 뒤에 오는 미생물 를 생각하자. 이때 이다. 두 미생물의 개체 수 차이 는 가 증가해도 감소하지 않는다.
Solution written by GPT6
-1일차에 개체 수 정렬에서도 가 먼저 온다면 이거나, 이고 이다. 더 늦은 일차에는 차이가 커지거나 같으므로 두 경우 모두 가 계속 먼저 온다. 따라서 어떤 표본이 한번 조건을 만족하면 이후에도 만족하며, 판정은 단조적이다.
성장 계수가 서로 다른 두 미생물에서 이면, 일차에 이다. 따라서 일차에는 두 미생물의 순서가 반드시 일치한다. 성장 계수가 같으면 개체 수의 차이가 변하지 않으므로 순서의 일치 여부도 변하지 않는다. 그러므로 어떤 일차에라도 가능한 표본은 일차에도 가능하다. 일차에 필요한 크기의 표본이 없다면 다른 어느 날에도 없고, 있다면 가장 빠른 일차는 에 있다.
고른 미생물을 성장 계수 순서대로 나열하면 의 부분 수열이 된다. 이 표본의 개체 수 정렬 순서가 같다는 것은 대응하는 쌍들이 엄격히 증가한다는 것과 동치이다. 따라서 가능한 표본과 증가 부분 수열은 서로 정확히 대응한다.
최장 증가 부분 수열을 구할 때 같은 길이의 부분 수열들 중 마지막 쌍이 작은 것을 남겨 두어도, 이후에 붙일 수 있는 쌍이 줄어들지 않는다. 현재 쌍 이상인 첫 마지막 쌍을 교체하면 그보다 짧은 부분 수열을 현재 쌍으로 늘릴 수 있고, 더 긴 부분 수열은 현재 쌍으로 끝날 수 없다. 이 불변식을 유지하면 배열의 길이는 정확히 최장 증가 부분 수열 길이가 된다. 따라서 판정은 정확하며, 단조적인 정확한 판정에 이분 탐색을 적용하면 요구한 가장 빠른 일차를 얻는다.