O(n) 시간과 O(1) 공간에서 중복 찾기: 심층 설명

제기된 문제는 중복을 식별하는 것과 관련됩니다 0부터 n-1까지의 숫자를 포함하는 배열 내의 요소입니다. 문제는 O(n) 시간 복잡도 내에서 일정한(O(1)) 메모리 공간만 사용하여 이를 효율적으로 달성하는 것입니다.

제시된 솔루션은 해시 테이블이나 기타 추가 데이터가 필요하지 않은 독창적인 기술을 사용합니다. 구조. 대신 배열 자체의 값을 활용하여 중복 요소를 식별하고 표시합니다.

1. 배열 치환:

   내부 루프는 다음 논리를 기반으로 하는 배열:

   while A[A[i]] != A[i]
       swap(A[i], A[A[i]])
   end while

   이 순열 단계는 요소 x가 배열에 존재하는 경우 해당 인스턴스 중 적어도 하나가 A[x]에 위치하도록 보장합니다. 이는 후속 단계에서 매우 중요합니다.

2. 중복 식별:

   외부 루프는 각 요소 A를 검사합니다.[i]:

   for i := 0 to n - 1
       if A[i] != i then
           print A[i]
       end if
   end for

   A[i] != i인 경우 i가 배열의 올바른 위치에 존재하지 않음을 의미합니다. 따라서 중복된 요소이므로 인쇄됩니다.

3. 시간 복잡도 분석:

   이 기술은 O(n) 시간에 실행됩니다. . 중첩 루프에는 n번 반복하는 외부 루프와 최대 n - 1번 반복을 수행하는 내부 루프가 있습니다(왜냐하면 각 스왑은 하나의 요소를 올바른 위치에 더 가깝게 가져오기 때문입니다). 따라서 총 반복 횟수는 n*(n - 1)로 제한되며 이는 O(n^2)이지만 n*(n - 1) = n^2 - n과 같이 O(n)으로 단순화할 수 있습니다. = n(n - 1) = n*n - n

4. 공간 복잡도 분석:

   알고리즘은 입력 크기와 관계없이 일정한 공간만 사용합니다. 중요한 통찰력은 순열에 활용되는 공간이 입력 배열 내에 이미 존재한다는 것입니다. 추가 저장 구조는 필요하지 않습니다.

5. 추가 참고 사항:

   • 알고리즘은 배열에 0부터 n까지의 정수가 포함되어 있다고 가정합니다. 1.
   • 중복이 있는 경우에도 시간 복잡도는 동일하게 유지됩니다.
   • 이 알고리즘은 중소 규모 배열에 효율적입니다. 대규모 배열의 경우 해시 테이블과 같은 데이터 구조를 사용하는 대체 접근 방식이 더 적합할 수 있습니다.