-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
6-D 시간복잡도 질문입니다.
23.06.04 19:21 작성 조회수 204
0
안녕하세요 선생님.
lower_bound나 upper_bound의 경우 vector의 크기가 n이면 시간복잡도가 n일 것 같은데
이 문제의 경우에
for(int i = 0; i < n; i++){
auto pos = lower_bound(v.begin()~~~)
~~~`
}
이면 시간 복잡도가 n^2로 이분탐색하는 것보다 더 클 것 같은데 맞나요?
답변을 작성해보세요.
0
큰돌
지식공유자2023.06.05
안녕하세요 개발님 ㅎㅎ
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점은 제가 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
답변 1