O (1) 런타임에서 가장 낮은 수 찾기 - java

Question

나는 링크 된 목록, 배열 및 상수 메모리 사용을 기반으로 데이터 구조를 만들 필요가 있습니다. M> N되도록 N과 M.

N은 디스크상의 키의 최대 용량을 나타내고, M은 컴퓨터 하드 드라이브는 최대를 나타낸다 : 입력으로서

나는 두 숫자를 얻는다. 삽입 -

1. 삽입 (데이터) :

   그래서 난 디스크 - 온 - 키 하드 드라이브에서 '이동'정보, 그 프로그램은 다음과 같은 방법을 구현하는 데 필요한 프로그램을 작성해야 디스크 - 온 - 키에 데이터, 만약 그것의 전체가 가장 중요한 데이터 (*) 제거 : 최악의 경우 실행 시간 O (1).

2. 삭제 (데이터) - (1)

(*) 사용자가 파일의 중요성을 변경할 수 있습니다 O - 디스크 - 온 - 키에서 주어진 데이터를 삭제합니다. 나는이 배열 [1 ... M] 것 '보류'컴퓨터 데이터를 생성 한

: 메모리 사용의

최대 금액은 지금까지 무슨 짓 (M)

O입니다 필자는 디스크 온 키 데이터를 보관할 이중 연결 목록을 만들었습니다. [생각은 : 데이터가 디스크 온 키에 추가 될 때마다 링크 된 목록에 추가 될 것이므로 배열을 색인 (/ 키) 저장소로 사용하여 데이터로 직접 이동할 수 있습니다.]

내 컴퓨터 데이터 필드 :

node firstNode; 
node currentNode; 
node[] dataCollection; // Will hold computer hard-drive data 

그래서 내가 [그래서 난 삽입에 사용 할 수 있습니다] 추가 할 데이터가 가장 중요한 데이터를 교체하는 방법을 창조하고 싶었다, 내 코드 교체를 위해 :

를

public void replace(int leastImportantdata, int insertData){ 
    node leastImportant = dataCollection[leastImportantdata]; 
    if (leastImportant.prev!=null) leastImportant.prev.next=dataCollection[insertData-1]; 
    if (leastImportant.next!=null) leastImportant.next.prev=dataCollection[insertData-1]; 
    numOfReplacements++; 

따라서 가장 중요한 문제는 두 가지 '결합 된'데이터 구조와 st O (1)의 런타임 유지, 특히 사용자가 파일 중요도를 변경하기로 결정한 경우

• 우리가 {4,3,2,1} (숫자는 중요도를 나타냄)로 시작한다고 가정하면 가장 중요한 데이터는 1이됩니다. 갑자기 사용자가 최종 파일 중요도를 5로 변경하기로 결정하면 { 4,3,2,5}이고 가장 중요하지 않은 데이터는 2입니다.

어떤 아이디어가 있습니까?

Answer 1

귀하의 목록에 필요한 최소한의 중요한 데이터를 찾아 낼 수 있으려면.

그래서 처음에는 연결된 목록의 순서가 중요합니까? 당신은 인덱스를 기반으로 데이터를 가져 오는 것으로 보이고 목록을 순회하지는 않습니다. (그 명령이 중요하다면 내 대답의 나머지 부분은별로 도움이되지 않을 수도 있습니다 : D).

이것은 잠재적으로 목록에 항목을 삽입 할 수 있으므로 목록의 머리글에 대한 참조가있는 한 일정한 성능으로 삭제할 항목을 얻을 수 있도록 우선 순위가 낮은 순서로 항목을 정렬 할 수 있음을 의미합니다. 명부.

이것은 불행히도 삽입의 복잡성을 증가시킵니다.이 우선 순위를 가진 링크 된 목록의 마지막 (잠재적으로 첫 번째) 파일에 우선 순위 맵을 유지할 수 있다는 것을 수정하십시오.

이 맵을 사용하면 새 파일을 삽입해야하는 위치를 즉시 파악하여 지속적인 성능을 얻을 수 있습니다.

그래서 3 개의 파일 P (A) = 1, P (B) = 3, P (C) = 3이면 맵은 1 -> (A, A) 3 -> (B, C) 우선 순위가 1 인 다른 파일을 삽입하려면 A를 따라야하고 우선 순위 2 인 파일을 삽입하려면 B보다 먼저 가야한다고 말하십시오.

분명히 유한 수의 가정이 가능합니다. 여기에 우선 순위가 있으며 사용 된 우선 순위 사이에 틈이 없음을 의미합니다.

희망이 해결하기 위해

Answer 2

내 제안을하는 데 도움이 (즉, 검색 요구) 문제는 다음과 같습니다

• 는 Comparable 인터페이스를 구현하는 노드 클래스를 정의합니다.

• 데이터 수집을 건너 뛰기 목록으로 구현하십시오. 가능하면 ConcurrentSkipListMap을 사용하여이 작업을 수행 할 수 있습니다.

SkipList 구현을 사용하면 항목이 중요도에 따라 정렬되도록 할 수 있습니다.

Java API doc에 따르면 doc -이 클래스 (ConcurrentSkipListMap)는 containsKey, get, put 및 remove 연산 및 해당 변형에 대해 예상되는 평균 log (n) 시간을 제공하는 SkipLists의 동시 변형을 구현합니다.

일반적으로 구현은 균형 이진 검색 트리 (즉, number of probes proportional to log n instead of n)와 비교하여 효율성이있는 항목 조회를 허용합니다.

마지막으로 SkipList에 대한 자세한 내용은 [here]으로, 사용자 고유의 구현 방법을 작성하십시오.