메디안 공간 복잡도

Question

Median of Medians를 사용하여 nth_number 선택 알고리즘을 구현했습니다. wikipedia에서 공간의 복잡성은 O (1)

중간 값을 중간 배열로 저장해야만 중간 값을 찾을 수 있습니다. 여분의 메모리를 사용하지 않고 어떻게 할 수 있습니까? 공간 복잡성 증가로 간주되지 않는 경우 설명하십시오.

function nth_number(v, n) { 
    var start = 0; 
    var end = v.length - 1; 
    var targetIndex = n - 1; 

    while(true) { 

     var medians = []; /* Extra memory. */ 

     /* Divide our array into groups of 5s. Find a median within each */ 
     for(var i = start; i <= end; i += 6) { 
      if(i + 5 < end) 
       medians.push(findMedian(v, i, i + 5)); 
      else 
       medians.push(findMedian(v, i, end)); 
     } 

     var median = findMedian(medians, 0, medians.length - 1); /* Find the median of all medians */ 

     var index = partition(v, median, start, end); 

     if(index === targetIndex) { 
      console.log(median); 
      return median; 
     } 
     else { 
      if(index < targetIndex) { 
       start = index + 1; 
       targetIndex -= index; 
      } 
      else { 
       end = index - 1; 
      } 
     } 
    } 
} 

Answer 1

선택 알고리즘은 일련의 파티션을 수행하기 때문에 입력 벡터를 다시 정렬해야합니다. 따라서 중간 값을 찾기 위해 입력 벡터를 재정렬하는 것이 가능하다고 가정하는 것이 합리적입니다.

하나의 간단한 전략은 5 개의 그룹을 연속으로 만드는 대신 인터리브하는 것입니다. 벡터가 N == 5K 요소가있는 경우에 따라서, 다섯 그룹은 다음과 같습니다

(0, k, 2k, 3k, 4k) 
(1, k+1, 2k+1, 3k+1, 4k+1) 
(2, k+2, 2k+2, 3k+2, 4k+2) 
... 
(k-1, 2k-1, 3k-1, 4k-1, 5k-1) 

다섯 그룹의 중간 값을 찾을 때 그런 다음 벡터 것을 의미한다 그룹의 첫 번째 요소로 교체 중간의 벡터는 다시 배열 된 벡터의 첫 번째 k 요소가됩니다.