자료구조론 - 기본 알고리즘 효율성 분석

🎯자료구조론 - 기본 알고리즘 효율성 분석

1. 알고리즘 효율성이 왜 중요할까?

우리가 어떤 문제를 해결할 때, 방법(알고리즘)은 다양합니다. 예를 들어 책에서 원하는 단어를 찾는 상황을 생각해보자.

방법 1 선형 탐색 : 첫 페이지부터 끝까지 한 장 한 장 넘기면서 찾기 → 최대 n번 확인해야 함.

방법 2 이진 탐색 : 사전처럼 정렬되어 있다면 중간 페이지부터 시작해서 절반씩 줄여가며 찾기 → 약 log n번만 확인하면 됨.

같은 문제라도 어떤 알고리즘을 쓰느냐에 따라 속도 차이가 수십~수백 배가 날 수 있다.

2. 알고리즘 효율성의 기준

(1) 시간 복잡도 (Time Complexity)

입력 크기 n이 커질 때 연산 횟수가 얼마나 늘어나는지 측정. 보통 점근적 표기법(Big-O)를 사용합니다.

표기법	의미	예시
O(1)	입력 크기와 상관없이 일정	배열에서 인덱스로 접근
O(log n)	입력이 커져도 조금씩만 늘어남	이진 탐색
O(n)	입력 크기만큼 늘어남	선형 탐색
O(n log n)	정렬 알고리즘에서 자주 등장	퀵정렬, 합병정렬
O(n²)	데이터가 조금만 커져도 급격히 증가	삽입정렬, 버블정렬

예시

• 배열 크기 1,000,000
  • 선형 탐색 O(n) : 최대 백만 번 확인
  • 이진 탐색 O(log n) : 약 20번 확인

(2) 공간 복잡도 (Space Complexity)

알고리즘이 실행되며 추가로 요구하는 메모리의 증가량(입력 자체를 저장하는 공간 제외).

• 구분
  • 총 공간(Total Space) = 입력 저장 + 보조 공간
  • 보조 공간(Auxiliary Space) = 알고리즘이 추가로 사용하는 공간

표기법	의미	대표 예시
O(1)	입력 크기와 무관하게 상수 크기의 보조 메모리	배열 원소 교환, 힙정렬(보조배열 없음)
O(log n)	재귀 호출 깊이에 비례한 스택 사용	퀵정렬(평균) 재귀 스택, 이진 트리 탐색(재귀)
O(n)	입력 크기에 선형 비례한 임시 구조체	합병정렬 보조배열, BFS의 방문배열/큐
O(n + k)	입력 n과 추가 파라미터 k에 의존	계수정렬(버킷 크기 k)

예시

• 합병 정렬 : 원본 크기만큼의 보조 배열 필요 → O(n)
• 퀵 정렬 : 추가 배열은 없지만 재귀 스택 필요 → O(log n)

3. 알고리즘 효율성 비교

알고리즘	시간 복잡도 (평균/최악)	공간 복잡도	특징
선형 탐색	O(n) / O(n)	O(1)	단순, 정렬 필요 없음
이진 탐색	O(log n) / O(log n)	O(1)	정렬 필요, 빠른 검색
삽입 정렬	O(n²) / O(n²)	O(1)	구현 단순, 작은 데이터에 적합
합병 정렬	O(n log n) / O(n log n)	O(n)	안정 정렬, 대규모 데이터
퀵 정렬	O(n log n) / O(n²)	O(log n)	평균적으로 가장 빠름

4. 실생활 비유

• O(1) : 냉장고에서 사과 꺼내기 (바로 찾음)
• O(log n) : 전화번호부에서 사람 찾기 (중간부터 반씩 줄여가기)
• O(n) : 책장을 처음부터 끝까지 다 뒤져서 책 찾기
• O(n²) : 모든 짝꿍 후보끼리 악수하기 (한 명이 모두와 인사해야 함)

5. 결론

• 알고리즘 효율성 분석은 단순히 이론이 아니라, 시스템 성능 최적화와 서비스 품질 향상을 위해 반드시 필요한 과정
• 시험에서는 공식적인 Big-O 분석을 강조하지만, 실제 프로젝트에서는 데이터 규모, 메모리 여유, 실행 환경 (PC vs 모바일, 단일 서버 vs 분산 시스템)도 함께 고려해야함.

📚 참고자료

• GeeksforGeeks
• Big-O Cheat Sheet