rhkdwo8492   2년 전

주어진 배열이 [15,20,25,30,40,55,65,80]이 있다고 하면 이진 탐색을 사용하여 80을 찾으려면 O(log2 n) 을 사용해서 3번 탐색만에 찾을 수 있는거 맞나요 맨처음 중앙값 30으로 비교한번 다음 55로 비교한번 다음 65로 비교한번 80으로 비교한번 해서 4번을 비교하게 되는데 이러면 log2 n보다 큰게 아닌가요...? 너무 헷갈리네요

cdw2241   2년 전

1번 정도 더하는 사소함에 너무 매달리지 맙시다

zenith82114   2년 전

찾는 값이 배열에 있는지 없는지 모르고 그것을 알기 위해 이분 탐색을 하는 경우도 있고, 있다는 건 아는데 어느 위치에 있는지 알고 싶을 때 이분 탐색을 하는 경우도 있습니다. 전자가 후자에 비해 정보가 적은 상황이므로 이 정보량의 차이가 마지막 비교 1번이 필요한지 아닌지를 가른다고 보시면 됩니다.

cr00   2년 전

https://en.wikipedia.org/wiki/...

big O 표기법은 정확한 횟수를 나타내는 게 아닙니다

댓글을 작성하려면 로그인해야 합니다.