배열의 항목을 찾는 평균 단계 수는 왜 N/2입니까?

Question

누군가 정렬되지 않은 배열 데이터 구조에서 항목을 찾는 평균 단계 수가 N/2 인 이유를 설명 할 수 있습니까?

Answer 1

명시된 질문은 잘못되었습니다. Linear search may perform better.

Answer 2

이것은 실제로 배열의 숫자에 대해 알고있는 내용에 달려 있습니다. 모든 확률 매스가 단일 값에있는 분포에서 모두 그려진 경우 모든 값이 같기 때문에 원하는 값을 찾기 위해 정확히 한 단계 만 거치게됩니다.

이제는 배열이 의 고유 한 값의 무작위 순열으로 채워지는 것을 매우 강력하게 가정 해 봅시다. 당신은 별개의 요소들의 임의의 정렬 된리스트를 선택하고 무작위로 그것을 치환하는 것으로 생각할 수 있습니다. 이 경우 실제로 존재하는 배열의 일부 요소를 검색한다고 가정합니다 (이 요소는 요소가 없으면 세분화됩니다). 그런 다음 취할 수있는 단계의 수는 X에 의해 주어지며, 여기서 X는 배열에있는 요소의 위치입니다. 단계 수의 평균은 그래서 식 주어진 우리가 모든 요소는 랜덤 순열에서 작성한 가정하고 있으므로

E[X] = 1 Pr[X = 1] + 2 Pr[X = 2] + ... + n Pr[X = n] 

주어진다 E [X],

Pr[X = 1] = Pr[X = 2] = ... = Pr[X = n] = 1/n 

인 작성자 :

E[X] = sum (i = 1 to n) i/n = (1/n) sum (i = 1 to n) i = (1/n) (n)(n + 1)/2 
    = (n + 1)/2 

내가 생각하기에 당신이 찾고있는 대답은 다음과 같습니다.

Answer 3

질문의 간단한 재구성을 고려 : 우리는 우리의 random이의 고른 분포를 가지고 있다고 가정하면

int sum = 0, i; 
for (i = 0; i < LARGE_NUM; i++) sum += random(n); 
sum /= LARGE_NUM; 

:

lim (i->inf) of (sum(from 1 to i of random(n)) /i) 

의 또는 C에서 제한 될 것입니다 무엇

값 ( 1에서 n까지의 각 값이 똑같이 생성 될 수 있음)이면 예상 결과는입니다.. 평균 N/2 이유 도시

Answer 4

아마도 단순한 예는 다음이다 : [5, 0, 9, 8, 1, 2, 7, 3, 4, 6] :

는 10 개 항목의 정렬되지 않은 배열을 가정한다. 이 숫자는 모두 [0..9]입니다.

배열이 정렬되지 않았으므로 (즉, 항목의 순서에 대해 알지 못함) 배열의 특정 항목을 찾을 수있는 유일한 방법은 선형 검색을 수행하는 것입니다. 첫 번째 항목부터 시작하여 찾고있는 것을 찾거나 끝까지 도달하십시오.

그럼 각 항목을 찾는 데 필요한 작업 수를 계산해 봅시다. 첫 번째 항목 (5)을 찾는 작업은 단 한 번만 수행됩니다. 두 번째 항목 (0)을 찾는 데는 두 번 걸립니다. 마지막 항목 (6)을 찾는 데는 10 번의 작업이 필요합니다. 10 개의 항목을 모두 찾는 데 필요한 작업의 총 수는 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 또는 55입니다. 평균은 55/10 또는 5.5입니다.

"선형 검색은 평균적으로 N/2 단계를 필요로합니다"라고 평범한 지혜는 여러 가지 가정을합니다.가장 큰 두 가지는 다음과 같습니다.

1. 찾고있는 항목이 배열에 있습니다. 항목이 배열에 없으면 N 단계를 거쳐 결정됩니다. 따라서 검색되지 않는 항목을 자주 찾고 있다면 검색 당 평균 단계 수가 N/2보다 훨씬 많을 것입니다.

2. 평균적으로 각 항목은 다른 항목만큼 자주 검색됩니다. 즉, "0"등으로 검색 할 때마다 "6"을 자주 검색합니다. 일부 항목이 다른 항목보다 훨씬 자주 조회되는 경우 검색 당 평균 단계 수가 더 자주 검색되는 항목 번호는 가장 자주 조회되는 항목의 위치에 따라 N/2보다 높거나 낮을 것입니다.

Answer 5

내가 templatetypedef이 경우 훨씬 간단 하나가, 가장 교훈적인 답이 있다고 생각하지만.

n = 2m 인 집합 {x1, x2, ..., xn}의 순열을 고려하십시오. 이제 당신이 찾고자하는 요소 xi를 가져 가라. xi가 인덱스 m-k에서 발생하는 각 순열에 대해, 대응하는 미러 이미지 순열이 있으며, xi는 인덱스 m + k에서 발생한다. 이러한 가능한 지수의 평균은 [(m - k) + (m + k)]/2 = m = n/2이다. 따라서 집합의 가능한 모든 순열의 평균은 n/2입니다.