파이썬 코딩 테스트를 위한 시간 복잡도 이해하기

코딩 테스트를 공부하다 보면 시간 복잡도라는 말이 자주 나오는데요.

 

파이썬의 시간 복잡도는 알고리즘이나 프로그램의 실행 시간을 분석하는 중요한 개념입니다.

 

하지만 저희가 궁금한 건 시간 복잡도를 분석하는 방법이기에 다른 건 생략하겠습니다.

 

시간 복잡도 분석 방법

파이썬에서 시간 복잡도를 분석하는 방법에는 여러 가지가 있습니다.

• 이론적 분석: 알고리즘의 구조를 분석하여 Big O 표기법으로 복잡도를 표현하는 방법입니다.
• 실험적 분석: 말 그대로 다양한 입력 크기를 주고 그에 따른 실행 시간을 측정하고 그래프로 표현하는 방법입니다.
• 코드 프로파일링: 파이썬의 내장 도구를 사용하여 코드의 실행 시간을 측정하는 방법입니다.

---

 

일반적으로 자주 사용할 분석 방법은 Big O 표기법 입니다.

 

O(1): 상수 시간

상수 시간 복잡도는 입력 크기에 관계없이 일정한 시간이 소요되는 연산을 의미합니다.

• 배열의 인덱스 접근
• 해시 테이블의 삽입 및 검색(평균적인 경우)
• 스택의 push와 pop연산

O(log n): 로그 시간

로그 시간 복잡도는 입력 크기가 증가함에 따라 실행 시간이 로그함수처럼 증가하는 알고리즘입니다.

• 이진검색
• 균형 이진 탐색 트리의 삽입, 삭제, 검색
• 힙(Heap)의 삽입과 삭제

O(n): 선형 시간

선형 시간 복잡도는 입력 크기에 비례하여 실행 시간이 증가하는 알고리즘을 의미합니다.

• 배열의 순차 검색
• 단일 연결 리스트의 순회
• 문자열의 길이 계산

O(n log n): 선형 로그 시간

선형 로그 시간 복잡도는 입력 크기에 로그를 곱한 만큼 실행 시간이 증가하는 알고리즘입니다.

• 효율적인 정렬 알고리즘(퀵 정렬, 병합 정렬)
• 힙 정렬
• 파이썬 내장 정렬 함수인 sorted()와 list.sort()는 Timsort 알고리즘을 사용합니다.
  • Timsort의 알고리즘은 평균적인 경우 O(n log n)입니다.

O(n^2): 이차 시간

이차 시간 복잡도는 입력 크기의 제곱에 비례하여 실행 시간이 증가하는 알고리즘을 나타냅니다.

• 버블 정렬, 선택 정렬, 삽입 정렬
• 중첩된 반복문을 사용하는 알고리즘

O(2^n): 지수 시간

지수 시간 복잡도는 입력 크기에 따라 실행 시간이 기하급수적으로 증가하는 알고리즘을 의미합니다.

• 부분 집합 생성
• 순열 생성

 

---

 

만약 문제를 풀다가 답은 맞는데 시간 초과가 뜬다면 시간 복잡도를 개선해야 합니다.

파이썬에서 시간 복잡도를 개선하는 방법에는 여러 가지가 있습니다.

1. 알고리즘 최적화
2. 적절한 자료구조
3. 파이썬의 내장 함수와 라이브러리 사용
4. 코드 프로파일링을 통한 병목 지점 식별 및 개선

 

 

# 이 글의 내용 중 일부는 Perplexity AI의 도움을 받아 정보를 수집하고 정리하였으며, 추가적인 연구와 개인적인 견해를 더하였습니다.