6-D 시간복잡도 질문입니다.

작성한 질문수 11

0

안녕하세요 개발님 ㅎㅎ

for(int i = 0; i < n; i++){
auto pos = lower_bound(v.begin()~~~)

~~~`

}

이부분은 O(nlogn)의 시간복잡도를 가집니다.

lower_bound는 logn의 시간복잡도를 갖기 때문입니다.

이분탐색 = lower_bound 라고 생각하시면 됩니다.

lower_bound의 내부구조를 볼까요?

template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::difference_type count, step;
  count = distance(first,last);
  while (count>0)
  {
    it = first; 
    step=count/2; 
    advance (it,step);
    if (*it<val) {                 // or: if (comp(*it,val)), for version (2)
      first=++it;
      count-=step+1;
    }
    else count=step;
  }
  return first;
}

이런식으로 자체적으로 이분탐색이 들어가 있는 것을 볼 수 있죠? (step을 /2 하면서..)

참고 부탁드립니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.