인프런 커뮤니티 질문&답변
작성한 질문수
5-B 코드질문있습니다.
해결된 질문
작성
·
81
0
안녕하세요 큰돌님.
큰돌님께서 다른 수강생의 질문에 답하신 내용에 대해 질문드리고 싶습니다.
while(true){
if(!s.size()){cout << "FRULA" << '\n'; return 0;}
int flag = s.find(a);
if(flag != string::npos){
s.erase(flag, a.size());
}
else
break;
}
큰돌님께선 문자열 S의 길이가 100만이고, 문자열 A의 길이가 1일 때, 해당 코드의 시간복잡도는 100만!이라고 하셨습니다.
erase와 find의 시간복잡도는 O(N)으로 알고 있습니다.
첫번째 턴 최대 O(100만) FIND + O(100만) ERASE,
두번째 턴 최대 O(99만) FIND + O(99만) ERASE,
.
.
.
이런식이면 O(N^2)이지 않나요?
어떻게 100만!이 시간복잡도가 되는지 궁금합니다.
그리고 FIND의 시간복잡도가 O(N)인게 잘 이해가 안됩니다.
그런데, 실제로는 O(N*M)이지 않나요? N은 찾아야 하는 문자열이 속한 문자열의 길이, M은 찾아야 하는 문자열의 길이.
어떻게 O(N)이 되는지 궁금합니다.
답변 2
0
안녕하세요 lego님 ㅎㅎ
큰돌님께선 문자열 S의 길이가 100만이고, 문자열 A의 길이가 1일 때, 해당 코드의 시간복잡도는 100만!이라고 하셨습니다.
>>
제 이전 답변을 보면 N^2으로 답변드렸는데.. 혹시 링크 부탁드려도 될까요?
제가 N!이라고 했다면 잘못 답변드린 것같습니다.
이런식이면 O(N^2)이지 않나요?
>> 네 맞습니다.
저코드 시간복잡도는
N+(N−M)+(N−2M)+…N + (N - M) ...
가 되어서.. 결국 O(N^2)이 됩니다.
그리고 FIND의 시간복잡도가 O(N)인게 잘 이해가 안됩니다.
>>
보통은 O(N)이라고 보시면 되지만 최악의 경우에는 O(N*M)이 맞습니다.
N이 문자열의 길이, M이 찾고자 하는 문자열이라고 했을 때
O(N+M)이며 보통의 M은 N보다 짧은 문자열이기 때문에 O(2N)이 되어 O(N)이 됩니다.
그러나 최악의 경우, 특정 패턴이 문자열 내에서 반복적으로 매치되고 불일치하는 상황이 발생하면 시간 복잡도가 O(N*M)이 될 수 있습니다.
해당 부분은 교안에 반영토록 하겠습니다.
감사합니다.
C++ string Find 함수가 O(N)이 될 수 있는 이유는 KMP 알고리즘을 사용했기 때문인가요?
>> 아닙니다. KMP는 사용하지 않고 내부적으로 부르트포스 알고리즘을 사용합니다.
보통은 문자열이 균일하게 분포되어있다고 가정했을 때
찾고자 하는 패턴이 텍스트에 고르게 분포되어 있어 패턴이 자주 일치하지 않는 경우, 단순한 브루트 포스 알고리즘도 평균적으로 O(N) 시간 복잡도를 가질 수 있습니다.
이는 각 비교가 대부분 한 번만 수행되고 패턴의 첫 문자가 일치하지 않으면 다음 문자로 바로 넘어가기 때문에 -> O(N + M) -> O(2N) -> O(N)이 됩니다.
0
안녕하세요, 인프런 AI 인턴입니다.
lego0313님의 질문에 답변드립니다.
문자열에서 find와 erase 연산의 시간 복잡도는 보통 O(N)으로 알려져 있습니다. 여기서 N은 문자열의 길이입니다. 그러나 큰돌님이 말씀하신 시간 복잡도 100만!에 대해서는 오해가 있는 것 같습니다. 실제로는 그렇게 크게 나오지 않습니다.
코드를 보면, 문자열 S 에서 문자열 A를 찾아서 지우는 작업을 못 찾을 때까지 반복합니다. 만약 문자열 A가 문자열 S 안에 매우 많이 포함되어 있다면, 이 반복 작업으로 인해 시간 복잡도가 높아질 수 있습니다. 하지만 그렇다 하더라도 팩토리얼(!) 시간 복잡도는 아니며, find와 erase가 각각 O(N) 시간에 수행되므로 이론상 최악의 경우 시간 복잡도는 O(N^2)에 가깝습니다.
find의 시간 복잡도에 대해서는, 찾아야 하는 문자열 A가 문자열 S 안에서 하나씩 비교될 때, 최악의 경우 문자열 S의 모든 위치에서 문자열 A의 모든 문자를 비교해보아야 하므로, 최악의 경우 O(N*M)이 될 수 있습니다. 여기서 N은 문자열 S의 길이, M은 찾고자 하는 문자열 A의 길이입니다.
단순한 문자열 검색 시나리오에서 find의 시간 복잡도가 O(N)으로 설명되는 경우가 많은데, 이는 평균적인 상황이나 특정 조건 하에서의 복잡도를 가리킬 때입니다. 실제로는 찾는 문자열의 길이에 따라 O(N*M)으로 나타날 수 있습니다.
큰돌님의 설명에서 언급된 100만!의 시간 복잡도와 관련된 부분은 정확한 상황 설명이나 추가적인 문맥이 없이는 정확한 해석이 어려울 수 있습니다만, 기본적으로 위에서 설명한 내용에 기반하여 이해해 주시면 도움이 될 것 같습니다.
감사합니다. 큰돌님.
먼저 100만! 이라는 답변이 달렸던 링크입니다.
https://www.inflearn.com/questions/1038421/5-b-erase-substr-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84-%EC%A7%88%EB%AC%B8%EB%93%9C%EB%A6%BD%EB%8B%88%EB%8B%A4
그리고 한 가지 궁금한게 있는데,
Find 함수가 O(N)이 될 수 있는 이유는 KMP 알고리즘을 사용했기 때문인가요?