점근적 표기법과 빅오(Big O) 표기법

요새 LeetCode로 문제를 푸는 코딩테스트 스터디를 진행 중입니다 ㅎㅎ

매주 화요일마다 5문제씩 푸는데, 초반에는 그래도 좀 풀만 했지만 뒤로 갈수록 배경 지식이 필요한 문제들이 많이 나오더라고요.

무지성으로 풀지 않기 위해 자료구조나 알고리즘의 이론적인 부분도 조금씩 공부하면서 풀어볼 예정입니다.

그래서 오늘 알고리즘 분석에 자주 쓰이는 점근적 표기법과 Big O 표기법을 정리해 보도록 하겠습니다.

 

목차

1. 점근적 표기법이란?
2. Big-O 표기법이란?
3. 자주 등장하는 복잡도 예시

 

점근적 표기법(Asymptotic Notation)이란?

점근적 표기법은 알고리즘의 시간 복잡도와 공간 복잡도를 입력 크기 n이 매우 커질 때를 분석하여, 성능의 변화를 평가하기 위해 사용하는 수학적 도구입니다. 이는 알고리즘의 실행 시간 또는 사용 공간이 입력 크기에 따라 어떻게 변화하는지를 추상적으로 표현합니다.

‘점근’이란 단어는 수학적으로 어떤 값에 점점 가까워지는 특성을 의미합니다. 점근적 표기법에서는 입력 크기 n이 커질수록 알고리즘의 실행 시간이 어떤 식으로 증가하는지를 추상적으로 표현합니다.

 

예를 들어 알고리즘의 실행 시간이 6n^2 + 100n + 300으로 표현된다고 가정해 봅시다.

이 때, 입력값 n = 20일때,

 

• 6n^2 = 2400
• 100n = 200
• 300 = 300

이 때, 6n^2이 전체 값의 대부분을 차지하며, 나머지 100n + 300의 영향은 상대적으로 미미해집니다. n이 더 커질수록 n^2이 기하급수적으로 커지기 때문에 이 차이는 더욱 명확해 집니다.

점근적 표기법에서는 알고리즘의 성능 분석에서 중요한 것은 입력 크기 n에 따른 성장률입니다. 계수 6은 특정 환경에서만 영향을 미칠 뿐이고, 작은 입력값에서만 유의미한 100n이나 상수 300은 입력 크기가 충분히 커지면 무시할 수 있습니다. 이로 인해 실행 시간은 주로 n^2에 의해 좌우됩니다.

 

이렇게 중요하지 않은 항과 상수 계수를 제거하면 이해를 방해하는 불필요한 부분이 없어져서 알고리즘의 실행 시간에서 중요한 부분인 성장률에 집중할 수 있습니다. 상수 계수와 중요하지 않은 항목을 제거한 것은 점근적 표기법이라고 합니다. 

 

점근적 표기법에는 세 가지의 주요 종류가 있습니다.

1. Big-O 표기법 (이 알고리즘은 아무리 오래 걸려도 이 정도를 넘어가지는 않는다. 상한선)
2. 오메가 표기법 (이 알고리즘은 최소한 이 정도는 걸린다. 하한선)
3. 세타 표기법 (이 알고리즘은 평균적으로 정확히 이 정도 걸린다.)

각 표기법은 알고리즘의 실행 시간이나 공간 사용량을 서로 다른 관점에서 분석하는 데 사용됩니다. 특히 코딩테스트에서는 어떤 입력이 주어질지 알 수 없으므로, 최악의 입력이 주어질 가능성을 항상 염두에 두어야 합니다.

이와 마찬가지로 실무에서도 시스템의 안정성과 확장성을 확보하기 위해 최악의 시나리오를 예상하는 것이 매우 중요합니다. 최악의 경우를 알고 있어야 시스템이 과부하 없이 안정적으로 동작할 수 있도록 설계할 수 있기 때문입니다.

이러한 이유로 코딩테스트와 실무 모두에서 최악의 경우를 기준으로 성능을 평가하는 Big-O 표기법이 자주 사용됩니다. 이제 Big-O 표기법에 대해 자세히 정리해 보겠습니다.

BIG-O 표기법이란?

Big-O 표기법은 알고리즘의 최악의 경우 시간 복잡도를 나타내는 수학적 표기법으로, 입력 크기 n이 매우 커질 때 알고리즘의 성능이 어떻게 증가하는지를 표현합니다. 이는 입력 데이터에 따라 성능이 달라질 수 있는 알고리즘에서, 최악의 시나리오를 기반으로 성능을 평가하는 데 사용됩니다.

 

Big-O 표기법은 T(n)이 알고리즘의 실행 시간을 나타낼 때, 다음 조건을 만족하는 함수 f(n)을 찾는 과정으로 정의됩니다

 

• T(n): 알고리즘의 실제 실행 시간 (혹은 공간 복잡도)
• f(n): Big-O로 표현되는 기준 함수
• c: 상수 계수 (Big-O를 적용하는 기준 값 조정)
• n₀: 특정 크기 이상의 입력 n부터 조건이 성립하도록 하는 기준 입력 크기

즉, Big-O 표기법은 알고리즘의 실행 시간이 기준 함수 f(n)의 배수로 제한됨을 의미합니다.

 

자주 등장하는 복잡도 예시

1. O(1) - 상수 시간 복잡도

입력 크기 n에 관계없이 항상 일정한 시간이 걸립니다. 즉, 실행 시간이 입력 크기와 무관합니다.

• 배열에서 첫 번째 원소 접근하기
• 변수의 값 할당

매우 빠른 알고리즘, 입력 크기와 무관하게 일정한 시간이 소요되므로 가장 이상적인 시간 복잡도입니다.

2. O(log n) - 로그 시간 복잡도

알고리즘이 입력 크기가 커짐에 따라 시간이 로그적으로 증가합니다. 이진 탐색 알고리즘에서 사용하는 시간 복잡도입니다. 예를 들어, 이진 탐색 알고리즘에서 사용하는 시간 복잡도입니다.

• 이진 탐색 (정렬된 배열에서 특정 값을 찾기)
• 이진 트리에서 노드 탐색

매우 효율적인 알고리즘으로, 입력 크기가 커지더라도 실행 시간이 급격히 증가하지 않습니다. 대규모 데이터에서도 잘 동작합니다.

3. O(n) - 선형 시간 복잡도

실행 시간이 입력 크기 n과 비례하여 증가합니다. 입력 크기가 두 배가 되면 실행 시간도 두 배로 증가합니다.

• 배열 또는 리스트에서 모든 원소를 순차적으로 탐색하는 경우 (배열의 합 구하기)
• 선형 탐색

입력 크기에 비례하는 시간이 걸리므로, 작은 크기의 데이터에 대해서는 빠르지만 입력이 커지면 상대적으로 시간이 많이 걸립니다.

4. O(n log n) - 선형 로그 시간 복잡도

실행 시간이 n log n 형태로 증가합니다. 이는 선형적인 시간과 로그 시간이 결합된 형태로, 매우 효율적입니다.

• 병합 정렬
• 퀵 정렬
• 힙 정렬

정렬 알고리즘에서 자주 등장하는 시간 복잡도로, 일반적으로 빠르고 효율적인 정렬 방식입니다. 입력 크기가 커지면 O(n^2) 방식보다 훨씬 효율적입니다.

5. O(n^2) - 이차 시간 복잡도

실행 시간이 입력 크기 n의 제곱에 비례하여 증가합니다. 일반적으로 중첩된 반복문에서 발생합니다.

• 버블 정렬
• 선택 정렬
• 삽입 정렬

작은 데이터에는 괜찮지만, 입력 크기가 커지면 성능이 급격히 저하됩니다. 일반적으로 비효율적인 알고리즘으로 간주됩니다.

6. O(n^3) - 세제곱 시간 복잡도

실행 시간이 입력 크기 n의 세제곱에 비례하여 증가합니다. 이는 보통 세 개의 중첩된 반복문에서 발생합니다.

• 행렬 곱셈
• 세 개의 중첩된 반복문을 사용하는 알고리즘

O(n^2)보다 더 비효율적이고, 큰 입력에 대해서는 실행 시간이 매우 오래 걸립니다.

7. O(2^n) - 지수 시간 복잡도

실행 시간이 입력 크기 n에 대해 지수적으로 증가합니다. 입력 크기가 증가할수록 실행 시간이 급격히 증가합니다.

• 피보나치 수열 (재귀적으로 계산할 때, 메모이제이션 없이)
• 부분 집합 문제나 해를 찾는 백트래킹 문제

매우 비효율적이며, 실용적으로는 거의 사용되지 않습니다. 대개 문제의 크기가 작을 때만 계산 가능합니다.

8. O(n!) - 팩토리얼 시간 복잡도

실행 시간이 입력 크기 n에 대해 팩토리얼로 증가합니다. 이는 입력 크기 증가에 따라 실행 시간이 급격히 커지는 매우 비효율적인 복잡도입니다.

• 여행 판매원 문제(TSP)에서 모든 경로를 탐색하는 경우
• 모든 순열을 생성하는 알고리즘

O(n!)복잡도를 가진 알고리즘은 입력 크기가 커지면 실행 불가능한 수준으로 시간이 오래 걸립니다.

복잡도	이름	특징	예시
O(1)	상수 시간	입력 크기와 관계 없이 일정 시간	배열 첫 번째 원소 접근, 변수 할당
O(log n)	로그 시간	입력 크기에 비례하는 로그적 증가	이진 탐색, 이진 트리 탐색
O(n)	선형 시간	입력 크기와 비례하는 시간	선형 탐색, 배열 합 계산
O(n log n)	선형 로그 시간	정렬 알고리즘에서 자주 등장	병합, 퀵, 힙 정렬
O(n^2)	이차 시간	두 개의 중첩된 반복문을 포함	버블, 선택, 삽입 정렬
O(n^3)	세제곱 시간	세 개의 중첩된 반복문 포함	기본 행렬 곱셈, 3중 반복문 사용 알고리즘
O(2^n)	지수 시간	매우 빠르게 증가하는 시간	피보나치 재귀 계산, 백 트래킹 문제
O(n!)	팩토리얼 시간	입력 크기 증가에 따라 급격히 증가	여행 판매원 문제, 순열 생성 알고리즘