값이 정렬 된 배열에 있는지 여부를 결정하는 데 어떤 시간이 있습니까?

StackOverflow https://stackoverflow.com/questions/470605

문제

5000 정수의 정렬 배열이 있습니다. 임의의 정수가 배열의 구성원인지 얼마나 빨리 알 수 있습니까? 일반적으로 대답, C와 Ruby는 좋을 것입니다.

배열 값은 형식입니다

c * c + 1

어디 c 1에서 5000까지의 정수가 될 수 있습니다.

예를 들어:

[2, 5, 10, 17, 26, 37, 50 ...]
도움이 되었습니까?

해결책

다른 사람들이 언급 한 바와 같이 이진 검색은 O (log2n)이며 재귀 적으로 코딩 할 수 있습니다. 

   BinarySearch(A[0..N-1], value, low, high) {
       if (high < low)
           return -1 // not found
       mid = (low + high) / 2
       if (A[mid] > value)
           return BinarySearch(A, value, low, mid-1)
       else if (A[mid] < value)
           return BinarySearch(A, value, mid+1, high)
       else
           return mid // found
   }

또는 반복적으로 :

   BinarySearch(A[0..N-1], value) {
       low = 0
       high = N - 1
       while (low <= high) {
           mid = (low + high) / 2
           if (A[mid] > value)
               high = mid - 1
           else if (A[mid] < value)
               low = mid + 1
           else
               return mid // found
       }
       return -1 // not found
   }

그러나 가능한 가장 빠른 방법을 찾고 있다면 sqrt(N-1) 당신의 숫자의. 5,000 단어의 메모리만으로도 이런 식으로 O (1) 조회를 달성 할 수 있습니다.

설명:

모든 숫자는 1에서 n까지의 정수 n에 대한 n^2 + 1 형식이므로 n 요소 테이블을 만들 수 있습니다. 위치의 요소 i^2 + 1이 배열에 있는지 여부를 지정합니다. 테이블은 간단한 길이 N으로 구현 될 수 있습니다. 그러나 일단 테이블이 있으면 모든 조회는 O (1)입니다.

예시:

파이썬의 샘플 코드는 다음과 같습니다.

import math

N = 5000
ar = [17, 26, 37, 50, 10001, 40001]

lookup_table = [0] * N

for val in ar:
    idx = int(math.sqrt(val - 1))
    lookup_table[idx] = 1

def val_exists(val):
    return lookup_table[int(math.sqrt(val - 1))] == 1

print val_exists(37)
print val_exists(65)
print val_exists(40001)
print val_exists(90001)

테이블을 구축하면 최대 o (n)가 발생하며 조회는 O (1)입니다.

다른 팁

c에 이진 검색을위한 로그 (n)

나는 그것이 O (const)라고 말할 것입니다! :)

임의의 숫자 r이 주어지면 양식 (n*n+1)으로 표시 될 수 있는지 여부를 확인하는 것은 사소한 일입니다. SQRT (R-1)가 정수인지 아닌지 확인하십시오!

(글쎄, 프로그래밍 언어가 정수 대 플로팅 포인트 번호를 다루는 데 약간의 복잡성을 도출 할 수 있지만 여전히 : 배열을 전혀 검색 할 필요는 없기 때문에 그 숫자가 전혀 검색 할 필요는 없습니다. 이 특별한 형태.)

기술적으로 고정 크기 어레이에서 요소를 찾는 복잡성은 로그 이후2 5000은 변하지 않을 것입니다.

이진 검색은 O (log n)입니다.

위키 백과

O (로그 n) 배열에 n 요소가있는 경우

그냥 확장하기 위해 : 그것은입니다 LG N 테스트입니다 통나무2 N. 그것은 그것을 만듭니다 영형(통나무 N). 왜요? 이진 검색의 각 시험은 배열을 반으로 나눕니다. 따라서 필요합니다 LG n 시험.

이진 검색을 사용하여 로그 (N) 검색 시간입니다. 

bool ContainsBinarySearch(int[] array, int value) {
  return Array.BinarySearch(arrray, value) >= 0;
}

Perl에서 :

값을 정적 해시에로드 한 다음 O (1)입니다.

조회 해시를 구축하십시오

lookup_hash {$ _} = 1 foreach (@original_array);

조회 구문

($ lookup_hash {$ lookup_value}) && print "O (1)에서 찾았습니다 - 여기에 루프가 없습니다 n";

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top