이진탐색 평균비교횟수를 구하는 공식이 있나요?

비공개 조회수 658 2019.09.22

순차탐색은 평균비교횟수를 구하는 공식이 있는데 이진탐색은 없네요...

답변자님,

정보를 공유해 주세요.

1 개 답변

순차탐색의 평균이 O(N) 이면, 이진 탐색은 O(Log N)이예요.

순차탐색 평균이 빅오 표기법으로 하지 않으면, N/2 겠죠.

마찬가지로 이진 탐색을 빅오 표기법으로 하지 않으면, 2/3 Log N 이 됩니다. (삼각형의 무게중심)

그런데 이런것이 다 공식이 있나요? 신기하네요. 이런것까지 공식을 찾아봐야 하다니.

2019.09.23.

도움이 되었다면 UP 눌러주세요!
UP이 많은 답변일수록 사용자들에게 더 많이 노출됩니다.

NAVER