종만북에서 KLIS 문제에서 정렬 없이 O(n^2) 시간안에 KLIS 문제를 해결할 수 있다고 했는데 그 방법이 뭘까요?
제가 생각해본 더 빠른 방법은 각각의 index에서 increasing 관계를 가지는 다음 index로 넘어갈 때 특정한 저장소에 미리 그 인덱스들을 사전 순으로 저장하는 것인데요, (즉 LIS를 컴퓨팅 하는 시간에 다음 인덱스들도 사전순으로 같이 저장.) 그래도 시간 복잡도는 결국 사전 순으로 저장하기위해 priority queue를 이용하거나 다 넣고 나서 정렬을 해야되기 때문에 O(n^2 logn)일것 같은데요..
아니면 혹시 이 방법이 amortized cost때문에 O(n^2)가 되는건가요? 사실 제가 위에 말한 방법의 시간 복잡도 계산이 어렵네요.
i를 선택한 뒤 다음 KLIS 후보들은 항상 decreasing order기 때문에 sort 할 필요가 없군요. 그러고보니 미리 저장하지 않고 KLIS를 구한 다음에 다시 다음 후보 index 대해서 조사할 때에도 다 구하고 뒤에서부터 조사하면 decreasing order라서 sort할 필요가 없겠군요.
espuer
종만북에서 KLIS 문제에서 정렬 없이 O(n^2) 시간안에 KLIS 문제를 해결할 수 있다고 했는데 그 방법이 뭘까요?
제가 생각해본 더 빠른 방법은 각각의 index에서 increasing 관계를 가지는 다음 index로 넘어갈 때 특정한 저장소에 미리 그 인덱스들을 사전 순으로 저장하는 것인데요, (즉 LIS를 컴퓨팅 하는 시간에 다음 인덱스들도 사전순으로 같이 저장.) 그래도 시간 복잡도는 결국 사전 순으로 저장하기위해 priority queue를 이용하거나 다 넣고 나서 정렬을 해야되기 때문에 O(n^2 logn)일것 같은데요..
아니면 혹시 이 방법이 amortized cost때문에 O(n^2)가 되는건가요? 사실 제가 위에 말한 방법의 시간 복잡도 계산이 어렵네요.
8년 전