왜 3/4*n인지가 도저히 이해가 안 갔다.
왜 이해가 안 갔냐면 책을 이상하게 읽어서 였다.
순차탐색의 평균 시간복잡도를 구한다는 뜻은
ㅁㅁㅁㅁㅁㅁㅁ
7개의 array가 있을때 원하는 Index를 찾건 못찾건 해당 순차탐색이 평균 몇번 도느냐를 구하는 것이다.
index를 찾았을때의 평균이 아니라.
해당 Index를 찾는지 못찾는지가 결정되는 For이 찾든 못찾든 평균적으로 몇에서 끝나냐를 구한다는 것이다.
즉 -> 못찾을 경우, 찾는경우 모든 경우를 합친 값의 평균을 구하라는 뜻이다.
먼저
가정 1 : 탐색 대상이 배열에 존재하지 않을 확률을 50%라고 가정한다.
가정 2 : 배열의 첫 요소부터 마지막 요소까지, 탐색 대상이 존재할 확률은 동일하다.
가정2가 혼돈 될 수 있는데 그냥 array에 다 공평한 확률로 존재한다는 거다. 확률에 개입할 외부적 요소가 없다는것
가정 1은 탐색대상이 배열에 있을 수 도 있고 없을 수도 있다는 것.
즉
ㅁㅁㅁㅁㅁㅁㅁ
. . . . . . .
. . . . . .
. . . . .
. . . .
. . .
. .
.
7개의 array를 가진 배열에서 순차탐색을 하여 원하는 Index를 찾을 때 평균
1번 2번 3번 4번 ...7번이니까 이를 다 더 한후 평균을 내면 대충 n/2의 값이 나온다. 몰론 대충이다. 숫자가 작을 수 록 N/2가 아닌 것처럼 보이지만 숫자가 커질 수록 결국 N/2에 가까워진다.
즉 원하는 Index를 찾을 평균 횟수는 은 n/2이다.
못찾을 횟수의 평균 -> 못찾으니까 N번 돌겠지 즉 n번이다.
여기서 가정 1를 적용해야한다.
너 근데 못찾을 수 도 있잖아? 못찾는 경우도 고려해줘야지
너 근데 혹시나 찾을 수도 있잖아, 찾는 경우도 고려해줘야지
찾는 경우 n/2
못찾는 경우 N
(찾는경우 + 못찾는경우)/2 = 평균경우, (찾을때 평균횟수+못찾을때 평균횟수)/2
(N/2+n) * 1/2 = 3/4 * n
