알고리즘과 복잡도 분석

1. 알고리즘의 조건

알고리즘은 문제를 해결하기 위한 유한한 절차이다.

• 입력: 0개 이상
• 출력: 1개 이상
• 명확성: 각 단계가 모호하지 않다.
• 유한성: 유한 단계 후 종료한다.
• 효과성: 각 연산이 실제로 수행 가능하다.

2. 시간복잡도와 공간복잡도

시간복잡도는 입력 크기 n이 증가할 때 기본 연산 횟수가 어떻게 증가하는지 나타낸다. 공간복잡도는 입력 외에 필요한 추가 메모리의 증가량을 나타낸다.

실행 시간을 초 단위로 재는 것보다 입력 크기에 따른 증가율을 비교하는 이유는 하드웨어와 구현 환경의 영향을 줄이기 위해서이다.

3. 점근 표기

• O(g(n)): 증가율의 점근적 상한
• Ω(g(n)): 점근적 하한
• Θ(g(n)): 상한과 하한이 같은 정확한 차수

전공 필기에서는 보통 최악 시간복잡도를 Big-O로 묻는다. 상수와 낮은 차수 항은 큰 n에서 영향이 작으므로 제거한다.

3n² + 5n + 7 → O(n²)

4. 대표 증가율

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

• O(1): 배열 인덱스 접근
• O(log n): 이진 탐색, 균형 트리 탐색
• O(n): 순차 탐색
• O(n log n): 병합정렬·평균 퀵정렬
• O(n²): 단순 이중 반복, 선택정렬

5. 코드 분석 방법

연속된 문장

시간복잡도를 더한 뒤 가장 큰 차수만 남긴다.

중첩 반복문

각 반복 횟수를 곱한다.

for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
        count++;

기본 연산이 n²번 수행되므로 O(n²)이다.

반복 변수가 배수로 증가

for (i = 1; i < n; i *= 2)
    count++;

2^k ≥ n이 되는 횟수만큼 반복하므로 O(log n)이다.

삼각형 반복

내부 반복이 1+2+...+n번이면 n(n+1)/2이므로 O(n²)이다.

6. 최선·평균·최악과 분할 상환

같은 알고리즘도 입력 상태에 따라 수행 시간이 달라질 수 있다. 예를 들어 퀵정렬은 평균 O(n log n)이지만 피벗 분할이 계속 불균형하면 O(n²)이 된다.

동적 배열의 끝 삽입은 가끔 O(n) 재할당이 필요하지만 여러 삽입에 걸친 평균 비용은 O(1)로 볼 수 있다. 이를 분할 상환 분석이라고 한다.

7. 입력 크기의 의미

복잡도에서 n이 무엇인지 먼저 정한다. 정수 값 N 자체가 아니라 N을 표현하는 비트 수가 입력 크기일 수 있다. 예를 들어 N까지 반복하는 알고리즘은 값 기준 O(N)이지만 이진 입력 길이 b=log N 기준으로는 O(2^b)일 수 있다.

8. 반복문 정밀 분석

for (i = 1; i <= n; i *= 2)
    for (j = 0; j < i; j++)
        count++;

내부 반복 합은 1+2+4+...≤2n이므로 O(n)이다. 바깥 반복이 O(log n)이라고 무조건 곱해 O(n log n)으로 판단하면 틀린다.

for (i = n; i > 1; i /= 2)
    for (j = 0; j < n; j++)
        count++;

이 경우 각 레벨에서 n번이므로 O(n log n)이다.

9. 재귀 관계와 마스터 정리 기초

T(n)=aT(n/b)+f(n)에서 재귀적으로 생기는 부분 문제의 총량 n^{log_b a}와 결합 비용 f(n)을 비교한다.

• 2T(n/2)+Θ(n) → Θ(n log n)
• T(n/2)+Θ(1) → Θ(log n)
• 2T(n/2)+Θ(n²) → Θ(n²)

모든 점화식에 마스터 정리를 적용할 수 있는 것은 아니다. T(n)=T(n-1)+n은 합을 직접 전개해 Θ(n²)이다.

10. 공간복잡도와 재귀 스택

입력 배열을 제외한 추가 공간을 보조 공간(auxiliary space)이라고 한다. 재귀 깊이가 d이고 각 호출이 O(1) 지역 공간을 쓰면 호출 스택은 O(d)이다.

• 재귀 이진 탐색: O(log n) 스택
• 편향 BST 재귀 순회: O(n) 스택 가능
• 병합정렬 배열 구현: O(n) 보조 배열 + O(log n) 스택

11. 분할 상환 분석 방법

• 총계법: 여러 연산의 전체 비용을 연산 수로 나눔
• 회계법: 싼 연산에 크레딧을 더 부과해 비싼 연산 비용을 미리 지불
• 잠재함수법: 자료구조 상태의 잠재 에너지 변화로 비용을 분석

동적 배열, 다중 pop 스택, Union-Find 등이 대표 적용 대상이다.

12. 복잡도 비교의 한계

O(n) 알고리즘이 작은 입력에서 항상 O(n log n)보다 빠른 것은 아니다. 그러나 n이 충분히 커질 때 증가율의 차이가 지배적이 된다. 또한 평균 복잡도는 입력 분포 가정이 필요하다.

최종 확인 문제

1. 코드 for(i=1;i<=n;i*=2) for(j=0;j<i;j++) x++;의 시간복잡도를 구하시오.
2. T(n)=T(n-1)+n의 시간복잡도를 구하시오.
3. T(n)=2T(n/2)+n²의 점근 복잡도를 구하시오.
4. 재귀 이진 탐색의 시간복잡도와 보조 공간복잡도를 각각 쓰시오.
5. 정수 N을 이진 문자열로 입력받아 1부터 N까지 반복하는 알고리즘이 입력 비트 길이 b 기준 지수시간인 이유를 설명하시오.