시간 복잡도의 기초: Big O를 아이처럼 쉽게 이해하기 🍬

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

알고리즘

대상자

• 대상: 알고리즘 학습자, 인터뷰 준비자, 초보 개발자
• 난이도: 중간 (기초 개념 설명 + 예제 중심)

핵심 요약

• 시간 복잡도는 "입력 크기가 커질수록 프로그램이 실행되는 단계 수"를 나타냄.
• 핵심 Big O:
• O(1): 상수 시간 (예: get_first(candies)),
• O(n): 선형 시간 (예: find_sour_candy(candies)),
• O(n²): 이중 루프 (예: find_duplicates(candies)),
• O(log n): 이진 검색 (예: binary_search(candies, target)).
• 알고리즘 선택의 핵심: 데이터 구조와 문제 유형에 따라 적절한 복잡도를 선택해야 함.

섹션별 세부 요약

1. 시간 복잡도의 개념

• 시간 복잡도는 "입력 크기(n)에 따라 실행 시간이 어떻게 변하는가"를 측정함.
• 예시:
• LEGO 블록을 하나씩 놓는 경우: O(n),
• 정렬된 뽑기장에서 반으로 나누며 검색: O(log n).
• Big O는 알고리즘의 성능을 추상화하여 비교하는 표준 지표.

2. 코드 예시 분석

• O(1): get_first(candies) → 항상 첫 번째 요소만 반환.
• O(n): find_sour_candy(candies) → 모든 요소를 순회해야 함.
• O(n²): find_duplicates(candies) → 이중 루프로 모든 쌍을 비교.
• O(log n): binary_search(candies, target) → 반복적으로 범위를 절반으로 줄임.

3. 시간 복잡도 표 및 데이터 구조별 예시

• 배열:
• Traversal → O(n),
• Merge Sort → O(n log n).
• 해시 테이블:
• Insert/Search/Delete → O(1) (평균).
• 트리:
• Inorder Traversal → O(n),
• Height 계산 → O(n).
• 그래프:
• DFS/BFS → O(V + E) (V: 정점, E: 간선).

결론

• 실무 팁:
• 정렬된 데이터는 O(log n) 알고리즘 (예: 이진 검색)을 사용,
• 중첩 루프를 피하고 O(n) 또는 O(n log n) 알고리즘을 선택,
• Big O는 알고리즘의 효율성을 측정하는 핵심 지표로, 성능 최적화에 필수.