변경리스트의 효율적인 횡단

Question

목록 변경 목록이 있습니다 - 추가 및 삭제. 목록은 거대 할 수 있습니다 - 10'000 항목.

9'000 변경 후 목록의 상태를 알고 싶습니다.

처음부터 9'000을 변경하기 위해 목록을 걸을 수있었습니다. 그것은 나에게 약간 오래 찢어 보인다.

항목 목록을 유지하고 추가 할 때 기록하고 삭제되었을 때 기록 할 수 있습니다. 그런 다음이 목록을 걸어 특정 변경 사항에서 목록에 무엇이 있는지 확인할 수 있습니다. 추가 및 삭제가 똑같이있을 가능성이 높으면 걸어 가야 할 목록 요소의 수를 절반으로 줄일 것입니다 ...

그러나 큰 O 표기법은 문제의 크기를 줄이는 것이 더 효율적이지 않다고 말합니다 (내가 올바르게 이해 한 경우).

100 번째 또는 1000 번째 변경마다 목록의 상태를 캐시 할 수 있습니다. 그러나 Big O는 항목 수를 'n'으로 나누는 것이 더 효율적이지 않다고 말합니다.

그렇다면이 작업을 수행하는 효율적인 방법은 무엇입니까? 효율적인 방법이 있습니까?

자세한 내용은:구체적으로, 나는 사용자 정의 할당으로 메모리 할당 / 거래를 추적하고 있습니다. 각 할당 / 거래는 목록의 이벤트입니다. 각 할당에는 고유 한 ID가 있습니다. 9'000 이벤트 이후에 현재 할당 된 내용을 알고 싶습니다.

나의 첫 번째 아이디어는 각 ID에 대해 할당 된 이벤트와 거래 이벤트를 저장하는 것이 었습니다. 그런 다음이 목록을 9000보다 큰 첫 번째 할당으로 걸어가는 것입니다. 그러나 내가 말했듯이, 이것은 내가 걸어야 할 항목의 수를 절반으로 줄일 수 있습니다.

나는 Mike F가 만든 요점을 좋아합니다 - 가장 가까운 100 번째 아이템에서 걷는 것은 일정 시간입니다 ...

Answer 1

Xth 변경마다 목록의 상태를 캐시하면 바이너리 컷을 수행하여 원하는 변경 사항을 경계로 한 두 개의 캐시 된 상태로 내려갈 수 있습니다. 그러면 대부분의 X 항목을 걸어 항목 자체로 이동합니다. 그것은 O (log n), 더 많은 것입니다.

그러나 더 일반적으로, 큰 o 복잡성을 줄이는 것은 끝이 아닌 수단입니다. 목록이 일반적으로 10,000 개 항목이라면 복잡성을 줄이든 더 빠르게 만들어서 N = 10,000에 빠르게 만드는 것에 대해 걱정해야합니다.

편집하다: 죄송합니다. 단지 귀하의 질문을 더 신중하게 읽었습니다. 100 개 항목마다 상태를 캐시하는 경우 검색하지 않으므로 바이너리 볶음을 할 필요조차 없습니다. 가장 가까운 캐시 상태로 직접 점프하고 최대 100 개의 항목을 걸어 항목에 도달합니다. 그 자체. 그래서 그것은 일정한 시간 알고리즘입니까?

Answer 2

어떤 종류의 구조와 함께 일하고 있습니까? 일반적인 데이터 구조를 걷는 효율적인 방법은 없지만 특정 구조에 대한 수천 개의 최적화 방법과 효율적인 방법이 있습니다.

그리고 네, O (N) 시간 복잡성 인 알고리즘이있는 경우 항목 수를 절반으로 줄이면 O (N) 복잡성에서 변경되지 않습니다. 그러나 각 새 항목은 효과의 절반만으로는 영향을 미칩니다. 원래. 큰 O 표기법은 알고리즘을 분류하는 좋은 방법이지만, 실제로는 엄청난 숫자를 제외하고는 효율성이 뛰어나지 않습니다. 수백만 개의 항목을 정렬하는 것 이외의 거의 모든 응용 프로그램에 대해 Mergesort보다 더 효율적으로)

Answer 3

'타임 스탬프'또는 각 삽입 및 삭제를 표시하면 변경 사항을 찾으려면 간단한 이동이 필요합니다 (O (N)).