[TIL-250520] 시간복잡도

시간 복잡도란?

 - 입력크기 n에 따라 걸리는 연산 시간이 어떻게 증가하는지 수학적으로 표현한다.

 - 보통은 Big-O표기 법으로 나타낸다.

---

시간 복잡도 설명 예시

O(1)	입력과 무관, 항상 일정 시간	변수 1개 출력
O(log n)	입력을 절반씩 줄임	이진 탐색
O(n)	입력 1개당 1번 연산	선형 탐색
O(n log n)	정렬 알고리즘에서 자주 나옴	병합 정렬, 퀵 정렬
O(n²)	이중 반복문	버블 정렬, 완전탐색
O(2ⁿ)	지수적 증가	부분집합 탐색
O(n!)	순열/조합 전체 탐색	TSP, 모든 순서 탐색

 

 

---

 

복잡도를 분석해보자!!

   1. 반복문 기준으로 분석 방법(O(n), O(n²))

 

 

for문 복잡도 분석

 

    2. 재귀 함수

 

---

 

데이터 크기 변화에 따른 실행시간 비교

n의 크기 : O(1) O(log n) O(n) O(n log n) O(n²) O(2ⁿ)

10	1	3.3	10	33.2	100	1024
100	1	6.6	100	664.4	10,000	1.27e30
1,000	1	9.9	1000	9965.8	1e6	매우 큼

---

실제 시간 측정 할 수 있는 방법?

 

 

---

자주 나오는 시간 복잡도 정리!

 

Big-O 의미 예시 계산 방법

O(1)	상수 시간	딕셔너리에서 값 찾기	한 번만 실행
O(log n)	로그 시간	이진 탐색	n을 2로 계속 나눔
O(n)	선형 시간	선형 탐색	한 번씩 전체 탐색
O(n log n)	로그 섞인 선형	병합 정렬, 퀵 정렬	분할: log n, 처리: n
O(n²)	이중 루프	버블 정렬	n × n
O(2ⁿ)	지수	부분집합, DFS	모든 선택 경우
O(n!)	순열 전체	여행자 문제	n개 순열

 

입력 크기 n 적절한 시간복잡도

n ≤ 10	O(n!), O(2ⁿ) 가능
n ≤ 100	O(n²) 가능
n ≤ 1,000	O(n log n), O(n²) 간당간당
n ≤ 10⁵	O(n log n) 이하
n ≤ 10⁶~10⁷	O(n) 이하
n > 10⁷	O(1), O(log n)만 가능

 

마무리!

항목 설명

시간복잡도	입력 크기에 따라 연산 횟수 얼마나 늘어나는지
분석 방법	반복문, 재귀 횟수 계산, 로그 분할 여부 확인
측정 도구	time.time(), 입력 크기 변화로 테스트
복잡도 기준	O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) 등
시간 초과 피하려면	n 크기에 맞는 적절한 복잡도 선택해야 함

---

나의 생각 정리 :

   -  오늘은 이론에 대해 확인 해봤는데, 추후 TIL 통해 알고리즘 별 문제 복잡도에 관해 고민할 예정이다.

   -  BigO 시간복잡도 계산에 따라 다양한 예제를 쳐보지는 못하고 내가 알고 있는 부분에 대해서만 분석 방법을

      기재하였기 때문에, 진도를 진행함에 따라 천천히 다시 공부해보고 풀어볼 예정이다.