나는 여기에서 해결책을 읽고 있었다 : https://leetcode.com/problems/merge-k-sorted-lists/solution/ k 정렬 된 연결 목록을 하나의 연결 목록으로 통합하는 방법에 대해.
사소한 해결책은 2 개의 연결 목록에 대한 작업을 수행하는 함수를 작성하고 처음 2 개 목록에서 호출 한 다음 이전 결과와 3 번째 연결 목록으로 다시 호출 한 다음 이전 결과와 4 번째 연결 목록 등으로 다시 호출하는 것입니다.
보다 효율적인 또 다른 솔루션은 다음을 수행하는 것입니다.
k목록을 페어링하고 각 쌍을 병합합니다.
첫 번째 페어링 후 목록은 평균 길이를 가진 k목록으로 병합 된 다음 , 등 으로 병합됩니다 .k/22N/kk/4k/8
최종 정렬 된 연결 목록을 얻을 때까지이 절차를 반복합니다.
제 질문은 두 번째가 더 효율적인 이유 입니다. 저는 우리가 다른 순서로 같은 일을하고 있다고 생각하기 때문에이 사실을 받아들이기를 거부합니다. 그 개선은 어디에서 왔습니까? 더 빨리 만들기 위해 어떤 사실을 사용 했습니까?
나는 마지막 코멘트에서 내 질문을 명확히했다.
i 번째 연결 목록의 l[i]길이가이고 모든 연결 목록의 총 길이 가라고 가정 해 보겠습니다 L. 또한 두 개의 순서가 지정된 목록의 양방향 병합에는 O(a+b)시간이 복잡 하다는 것을 알고 있다고 가정합니다 . 여기서는 a첫 번째 목록의 길이이고 두 번째 목록 b의 길이입니다.
두 번째 솔루션 (솔루션 2)은 입력 데이터가 배열되는 방식에 관계없이 안정적인 시간 복잡도를 갖습니다. 연결 목록의 내용은 log k답변을 얻기 전에 여러 번 병합 되었으므로 O(L log k)모든 경우에 전체 시간 복잡성이 있습니다.
이제 첫 번째 솔루션 (솔루션 1)을 고려해 보겠습니다. 모두 l[i]가 같은 경우 (모든 연결 목록의 길이가 같음) 를 고려하면 총 시간 비용 T은 다음과 같습니다.
T = l[1] * k + l[2] * (k-1) + ... + l[k] * 1
= l[1] * k(k+1) / 2
= L * (k+1)/2
즉, 솔루션 1의 최악의 경우 시간 복잡성은 O(Lk)이며 이는 분명히 더 느립니다.
솔루션 1의 직접적인 개선은 길이에 따라 목록을 병합하는 것이지만 실제로는 도움이되지 않습니다. 길이에 따른 목록 정렬은 자유롭지 않으며, 앞서 언급 한 경우 분명히 도움이되지 않으므로 최악의 시간 복잡성이 개선되지 않습니다.
솔루션 2는 최악의 경우와 대부분의 경우에 더 좋습니다. 솔루션 1이 더 빠른 경우를 구성 할 수 있지만 솔루션 1이 전체적으로 더 나은 것은 아닙니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다