[1주차] 시간 복잡도

시간 복잡도

▶ 문제를 해결하는데 걸리는 시간과 입력의 함수 관계, 알고리즘이 입력 크기(n)에 따라 실행되는 데 걸리는 시간을 수학적으로 표현한 것

 

필요한 이유?

▶ 같은 문제를 풀더라도 알고리즘마다 속도가 다르다.

▶ 입력 데이터가 커질수록 실행 속도 차이가 커진다.

∴ 처리속도와 효율성, 최적화를 위해서 필요하다.

 

표기법

▶ 시간 복잡도는 빅오(Big-O) 표기법으로 표현

 

가장 빠르게 증가하는 항만 남기고 상수 계수는 무시합니다.

ex) 2n² + 6n + 10 → O(n²) 으로 표현

 

복잡도 이름 예시

O(1)	상수 시간	배열에서 인덱스로 접근
O(log n)	로그 시간	이진 탐색
O(n)	선형 시간	배열 전체 순회
O(n log n)	로그 선형 시간	효율적인 정렬(퀵정렬, 병합정렬)
O(n²)	제곱 시간	이중 반복문 (버블 정렬, 삽입 정렬)
O(2^n)	지수 시간	모든 부분 집합 탐색 (DFS 백트래킹 일부)
O(n!)	팩토리얼 시간	순열 전부 탐색

 

배열 [1, 2, 3, ..., n]이 있다고 할 때:

• arr[0] 접근 → O(1) => n은 arr[0] 단 한개를 의미하므로 = 1
• arr 전체 순회 → O(n) => (1~n까지) n 전체를 의미
• 이중 for문으로 모든 쌍 확인 → O(n²) => 1~n * 1~n = n²
• 정렬 후 이진 탐색 → O(n log n) + O(log n) ≈ O(n log n)

 

시간 복잡도 그래프

 

위에 그래프만 봐도 O(n)까지는 서서히 올라가지만, 그 이상 부터는 급격하게 올라가는 것을 알 수 있다.

 

마치며

스터디를 위해서 시간복잡도에 대해서 개념을 알아봤다.

일단, 이러한 것이 있다는 걸 알고 스터디 진행하면서 다시 이해하자