Cộng đồng Hỏi & Đáp của Inflearn

안녕하세요 재윤님 ㅎㅎ

C++ 교안에 'sort()의 시간 복잡도는 O(nlogn) 이다.' 이런식으로 각 함수별 시간복잡도가 기재되어있던데, 코테에서 사용하는 함수가 상당히 많은데, 각 함수마다 시간복잡도 얼마인지 전부 외워야
-> 네 그렇긴한데요. 교안 1회독 이후에 개념 + 문제풀이 하시다보면 자연스레 외워질거에요.

감사합니다.

안녕하세요, 인프런 AI 인턴입니다. 재윤님.

코딩 테스트에서는 여러 가지 표준 라이브러리 함수의 시간 복잡도를 알고 있는 것이 매우 유용합니다. 특히 자주 사용되는 함수들에 대해서는 기본적으로 알고 계시는 것이 문제 해결에 큰 도움이 됩니다. 그러나 모든 함수의 시간 복잡도를 외우는 것보다는 핵심적인 몇 가지를 이해하고 있는 것이 더 중요합니다.

주요 함수와 시간복잡도

몇 가지 자주 사용되는 함수와 그 시간 복잡도를 말씀드리겠습니다:

1. sort(): 일반적인 C++ std::sort()의 시간 복잡도는 평균적으로 O(n log n)입니다. 이는 빠른 정렬 알고리즘인 퀵소트 기반으로 구현되어 있기 때문입니다.

2. binary_search(): 이진 탐색의 시간 복잡도는 O(log n)입니다. 정렬된 배열에서 특정 요소를 찾는 데 유용합니다.

3. unordered_map: 대부분의 연산에 대해 평균 O(1)의 시간 복잡도를 가지며, 이는 결합, 탐색, 삽입 작업에 매우 효율적입니다.

4. vector:

   • 요소 추가 및 제거: 끝에 원소를 추가 또는 제거하는 push_back()과 pop_back()은 평균 O(1)입니다.
     
   • 특정 위치에 원소를 삽입 또는 제거하는 작업은 O(n)입니다.
     

전체 암기는 비효율적

모든 함수를 외우는 것은 비효율적일 수 있습니다. 대신:

• 기본 함수: 자주 사용하는 함수와 알고리즘의 시간 복잡도는 기억합니다.
  
• 문서 활용: 문제가 생기면 공식 문서나 참고 문헌을 빠르게 체크할 수 있게 준비합니다.
  
• 연습 문제: 실제로 문제를 푸는 과정을 통해 자연스럽게 학습합니다.
  

관련 참고 자료:

• 10주완성 C++ 코딩테스트 중 시간복잡도 이해 - 시간복잡도에 대한 이해와 방법론 제시.
  

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.