알고리즘 성능 분석: Big O 표기법 가이드

"이 코드는 돌려봐야 얼마나 빠른지 알 수 있어요." -> 아마추어입니다. "이 코드는 시간 복잡도가 O(n log n)이라서 데이터가 100만 개 늘어나도 꽤 빠릅니다." -> 프로입니다. Big O 표기법은 알고리즘의 효율성을 데이터 개수(n)에 따른 연산 횟수의 증가율로 표현한 것입니다.

1. 주요 시간 복잡도 (빠른 순서)

• O(1) - Constant: 데이터가 100억 개라도 한 방에 찾습니다. (예: 배열 인덱스 접근, 해시 테이블 접근)
• O(log n) - Logarithmic: 데이터가 늘어날수록 효율이 기하급수적으로 좋아집니다. (예: 이진 탐색)
• O(n) - Linear: 데이터 개수만큼 비례해서 시간이 걸립니다. (예: for 문 한 번)
• O(n log n) - Linearithmic: 효율적인 정렬 알고리즘들의 평균 속도입니다. (예: 퀵 정렬, 병합 정렬)
• O(n^2) - Quadratic: for 문이 두 번 중첩된 경우입니다. 데이터가 조금만 많아져도 느려집니다. (예: 버블 정렬)
• O(2^n) - Exponential: 피보나치 수열 재귀 호출. 데이터가 늘어나면 지옥이 펼쳐집니다.

2. 공간 복잡도

시간뿐만 아니라 메모리를 얼마나 쓰는지도 중요합니다. "변수를 얼마나 더 만드는가"를 봅니다. 재귀 함수는 스택 메모리를 잡아먹으므로 공간 복잡도에 영향을 줍니다.

3. Big O를 줄이는 팁

• 중첩 루프는 피할 수 없다면 피하세요 (O(n^2) -> O(n)). HashMap을 써서 조회 속도를 O(1)로 줄이는 것이 대표적인 트레이드오프 기법(공간을 쓰고 시간을 산다)입니다.
• 불필요한 연산을 반복문 밖으로 빼세요.

알고리즘 문제 풀이(PS)뿐만 아니라, 백엔드 로직을 짤 때도 "이게 사용자가 10만 명일 때도 버틸까?"를 끊임없이 고민해야 합니다.