어떻게 링크드리스트에서 검색 시간을 줄일 수 있습니까?

Question

나는 직업 컵에이 질문을 읽었지만 'SkipList'이외의 좋은 대답을 찾지 못했습니다. 위키 피 디아에서 발견 된 SkipList에 대한 설명은 흥미 롭습니다. 그러나 'geometric/binomial distrubution'과 같은 용어를 이해하지 못했습니다. 나는 그것이 무엇인지 읽고 확률 론적 이론에 깊이 들어가 있습니다. 나는 단순히 좀 더 빨리 검색 할 수있는 방법을 구현하기를 원했다. 그래서 내가 한 일은 다음과 같습니다. 1. 생성 된 색인. - 1000 개의 노드를 만드는 함수를 작성했습니다. 그런 다음 연결된 목록 유형의 배열을 만들고 1000 개의 노드를 반복하고 23 번째 요소 (임의의 숫자가 마음에 들었습니다)를 선택하고 내가 '색인'이라고 부르는 배열에 추가했습니다.

private static void createIndex(SLL[] index, SLL head){ 
    int count=0; 
    SLL temp = head; 
    while(temp!=null) 
    { 
     count++; 
     temp = temp.next; 
     if((count==23){ 
      index[i] = temp; 
      i++; 
      count=0; 
     } 
    }  
} 

이제 마지막으로 '찾기'기능 :

SLL index = new SLL[50] 

이제 함수는 인덱스를 생성 할 수 있습니다. 이 함수에서, 먼저 769와 같이 입력 요소를 취합니다. 나는 'index'배열을 살펴보고 index [i]> 769를 찾는다. 따라서 이제는 head = index [i-1] 및 tail = index [i]를 'find'함수에 전달합니다. 그러면 769 개의 ​​짧은 요소 23 개를 검색 할 것입니다. 따라서 배열 점프와 node = node.next 점프를 포함하여 총 43 개의 점프가 필요하다고 생각되면 원하는 요소를 찾았습니다 769 점프.

참고 : 색인 배열을 만드는 코드는 검색의 일부가 아니므로 '찾기'기능의 시간 복잡도에 따라 시간이 복잡해집니다 (끔찍합니다). 이 색인 생성은 목록이 작성된 후에 별도의 함수로 수행되어야한다고 가정합니다. 또는 적시에 수행하십시오. 마치 웹 페이지가 Google 검색에 표시되는 데 시간이 걸리는 것 같습니다. 또한이 질문은 Microsoft 인터뷰에서 물었고 내가 제공 한 솔루션이 좋을지 아니면 그런 종류의 솔루션을 제공하는 바보처럼 보이는지 궁금합니다. 이 솔루션은 Java로 작성되었습니다. 피드백을 기다리는 중입니다.

Answer 1

여기에서 해결하려는 문제 또는 해결 방법이 무엇인지 알아내는 것은 어렵습니다. (힌트 : 전체 작업 코드는 모두 도움이 될 것이다!)

그러나 우리가 말할 수있는 일반적인 몇 가지가 있습니다 :

• 당신은 목록 데이터 구조를 검색 할 수 없습니다은 (예에서 i을 찾을 수 목록) 어떤 종류의 주문하지 않는 한 더 O(N). 예를 들어, 요소를 정렬합니다. (즉, 위치 i의 요소가 O(1)입니다 점점)리스트의 요소를 분류하고 목록이 색인 경우

• , 당신은 이진 검색을 사용하고 O(logN)의 요소를 찾을 수 있습니다.

• 더 나은 링크 된 목록의 i 위치에있는 요소를 가져올 수 없습니다. O(N).

당신은, 당신이 잠재적으로 더 많은 저장 공간의 비용으로 특정 작업 ... 더 나은 성능을 얻을 수있는 보조 데이터 (어떤 인덱스)를 추가하고, 기타 특정 작업이 더 비싼 만드는 경우. 그러나 더 이상 목록/링크 된 목록이 없습니다. 전체 데이터 구조는 "다른 것"입니다.