나는 양수 세트를 가지고 있습니다. 세트에 포함되지 않은 숫자가 주어지면, 이 인 다음으로 작은 다음으로 큰 숫자를 찾으려고합니다. 내가 지금 할 수있는 유일한 방법은 세트에서 숫자를 찾을 때까지 1 씩 감소시켜 다음으로 작은 것을 찾은 후 다음으로 큰 것을 찾는 것에 대해 동일한 작업을 수행하는 것입니다.세트에서 다음으로 작은 숫자와 가장 큰 숫자를 찾는 빠른 알고리즘
동기 부여 : 나는 날짜별로 키가있는 해시 맵에 많은 데이터를 가지고 있습니다. 나는 모든 단일 날짜에 대해 데이터 포인트를 가지고 있지 않습니다. 예를 들어 10/01/2000의 데이터가 60이고 10/05/2000의 데이터가 68 인 경우 10/02/2000을 요청하면 선형으로 보간하려고합니다. 나는 62를 가져야한다.
설정이 정렬되어 있는지 여부에 따라 다릅니다.
집합이 정렬되지 않은 경우 가장 가까운 (상위 및 하위) 연산은 O (n) 연산과 매우 간단한 알고리즘입니다.
집합이 정렬 된 경우 수정 된 이분 검색을 사용하여 O (log n)에서 답을 찾을 수 있습니다. 특히 더 큰 세트의 경우 훨씬 더 좋습니다.
이 작업을 반복적으로 수행하는 경우 집합을 정렬 할 가치가있을 수 있습니다. 이는 집합이 변경되는 빈도에 따라 한 번 또는 수천 가지가 아닌 O (n log n) 비용을 발생시킵니다. 어떤 종류의 나무 정렬은 새 항목이 추가 될 때 미래 정렬을 향상시키는 데 도움이 될 수 있습니다.
AVL 트리, red-black tree 또는 B +/B- 트리와 같은 데이터 항목을 트리에 넣으십시오. 그런 다음 정렬 된 값을 검색 할 수 있습니다.
배열에서 키를 가져온 경우 배열을 정렬하고 원하는 요소보다 작은 마지막 요소의 인덱스를 찾을 수 있습니다. 그런 다음 원하는 지점 바로 앞에있는 키의 색인을 알게되고, 그 다음 요소는 직후의 색인입니다.
이렇게하면 보간하기에 충분합니다.
(사용되는 데이터 구조는 배열 일 필요는 없으며, 다른 것들에 의해 제안 된대로 균형 잡힌 이진 트리가 이상적입니다. 특히 나중에 데이터를 다시 사용할 계획이라면 더욱 그렇습니다).
숫자를 정렬 한 다음 각 키에 대해 이진 검색을 수행하여 세트를 양분합니다. 누락 된 키의 양쪽에있는 숫자를 찾을 수 있습니다.
집합을 목록으로 변환하고 정렬 한 다음 집합에없는 번호에 대해 이진 검색을 실행합니다. 결과는 삽입 지점, 즉 숫자가있을 경우 존재할 위치입니다. 해당 n을 호출하면 정렬 된 목록의 인덱스 n의 요소가 그 다음으로 작은 숫자이고 정렬 된 목록의 인덱스 n+1의 요소가 그 다음으로 큰 숫자입니다.
구성 할 때 집합을 정렬 된 순서로 유지하면이 작업을 수행 할 수 있습니다. 그러면 삽입 지점을 쉽게 찾을 수 있습니다. 이 접근법은 예를 들어, floorEntry() 및 ceilingEntry() Java의 TreeMap 메소드.
집합을 정렬 된 목록/배열로 유지하고 bisection-search를 수행합니다. 예를 들어 파이썬에서는 정렬 된 목록이 있고 표준 파이썬 라이브러리의 bisect 모듈은 필요에 맞게 필요합니다.
데이터 정렬이 가능하다면이 모든 것은 binary search입니다. 두 가지 옵션이 있습니다. 정렬 된 컨테이너
당신이 정렬 된 용기에 숫자를 유지하는 경우
이 꽤 쉽다. HashMap을 사용하는 대신 데이터를 TreeMap에 넣으면 다음 하위 또는 다음 상위 요소를 효율적으로 찾을 수 있습니다.자바는 심지어 당신이 원하는 것을 정확히 할 수있는 방법이 있습니다 TreeMap는 내부적으로 red-black tree (balanced binary search tree의 일종)를 사용하기 때문에이 효율적입니다
. higherKey 및 lowerKey은 루트에서 시작하여 트리를 통과하여 요소가 있어야하는 위치를 찾습니다.
은 당신이 사용중인 언어를 잘 모르겠지만, C에서 + + 당신은 std::map을 사용하고, 유사한 방법은 다음과 같습니다
iterator lower_bound(const key_type& k)iterator upper_bound(const key_type& k)배열 + 정렬
항상 데이터를 정렬하지 않으려면 언제든지 d 배열 (또는 랜덤 액세스 용기), sort를 사용하고 배열에있는 STL의 이진 검색 루틴을 사용으로 ATA는 :
자바에서는 아날로그가 될 것이다 ArrayList에 항목을 덤프하려면 Java의 sort()을 호출 한 다음 binarySearch()을 사용하십시오.
모든 검색 루틴은 여기 O (logn) 시간이다. 데이터를 정렬 된 상태로 유지하는 데 드는 비용은 O (nlogn)이며 정렬 된 컨테이너 또는 배열을 사용합니다. 선별 된 컨테이너의 경우, 원가는 n 삽입을 통해 상각됩니다. 배열을 사용하면 sort()에 전화하면 즉시 요금을 지불합니다. 당신이 전혀 일을 정렬 할 수없는 경우
, 당신은 항상 linear search 사용할 수 있지만이 많이 사용의 경우에 O (n)이 알고리즘의 당신은 지불 할 것입니다.
정렬되지 않은 집합에서 n 번째 요소를 찾는 것은 O (n)입니다.(Select Algorithm) 여기서 가장 작은 다음 요소가 항상 가장 작은 & 인 경우 간단하고 덜 일반적인 알고리즘을 사용하면됩니다. 그러나 일반적으로 정렬되지 않은 목록 내에서 가장 작은, 두 번째로 작은 등의 요소를 찾는 것은 O (n)입니다.
이 요소를 색인 다음 세트를 정렬하고, (당신은 ... 당신의 알고리즘 클래스에서이 가르쳐되어 있어야합니다)는 소트 세트의 요소를 찾기
(N 로그 n) O O (로그입니다 n) (이진 탐색)
그는 i 번째 요소를 요구하지 않습니다. 그는 임의의 요소를 요구하고 있으므로 선택 알고리즘을 사용하는 데 이점이 없습니다. 증분 정렬을 수행하는 선택 알고리즘을 사용하지 않으면 i = 1에서 n까지 선택을해야합니다. O (n^2) 최악의 경우입니다. – tgamblin
"그는 i 번째 요소를 요구하지 않으며, 그는 임의의 요소"...를 묻습니다. 이 두 가지는 동일한 것을 의미합니다. i 번째 요소는 임의의 요소입니다. 그렇지 않으면 첫 번째 또는 두 번째 요소를 말했을 것입니다. i를 원하는 요소로 바꿉니다. 자, 그가 전체 집합 (그가 자신의 직책에서 지정하지 않은)에 대해이 작업을 수행하려면 O (n * log (n)) 정렬이 더 나은 방법이 될 것입니다. – Thanatos
매주 말에 대한 데이터 포인트가 항상 있다는 것을 알고 있다면 HashMap을 그대로 유지하고 제안한 것을 수행하십시오 ... 일정 시간 작동 검색 데이터의 각면에서 7 일 동안 검색하는 14 개의 해시 테이블 조회를 수행 할 것이므로 각각은 O (1) 원시 연산을 사용합니다.
데이터가 얼마나 밀도가 있고 RAM에 유지할 수 있는지 알 수없는 경우 많은 다른 사람들이 제안한 것처럼 균형 잡힌 트리 구조로 배치하십시오. 그러나 날짜가 많고 데이터베이스에서 네트워크를 통해 데이터를로드해야하는 경우 비용이 많이 듭니다.
"가장 가까운 (상한 및 하한) 연산이 O (n) 연산"임을 명확히합니다. 정렬되지 않은 배열에서 n 번째 요소를 찾는 것은 O (n) 연산이지만 알고리즘을 이해하는 데 다소 시간이 걸립니다. 그러나 분/초를 찾는 것은 매우 간단합니다. – Thanatos
사용중인 언어로지도를 반복 할 수 있습니다. 반복은 O (n) 연산입니다. 정말 이상한 데이터 구조 나 언어를 사용하지 않는 한 더 비싸게 만들 수 있습니다. Java의 HashMaps는 O (n)에서 반복 될 수 있습니다. – cletus
그는 데이터가 HashMap, 즉 정렬되지 않은 컨테이너에 있다고 씁니다. 크기에 따라 정렬 (O (n log n))은 그가 제시 한 것과 같이 인접한 키를 탐색하는 것과 비교할 때 상당히 비쌉니다 (아래 내 답변 참조). –