1. 두 번 도는 반복문에서 시작한 Big-O
해설글
작성 · 3분 읽기 · 조회수 —수정
기초 개념과 예제를 보강하고 시리즈 흐름을 연결
같은 결과를 더 적은 계산으로 만드는 문제
입력 배열이 [2, 4, 6, 8]이고, 각 위치까지의 평균을 모두 구한다고 하자. 원하는 결과는 [2, 3, 4, 5]다. 첫 번째 결과는 2, 두 번째는 (2+4)/2, 마지막은 (2+4+6+8)/4다.
가장 곧바른 방법은 매 위치에서 배열의 처음으로 돌아가 다시 더하는 것이다. 다른 방법은 앞에서 구한 합이나 평균을 이어받아 새 값 하나만 더한다. 둘 다 같은 답을 만들지만 입력이 길어질수록 필요한 계산 수가 크게 달라진다.
여기서 입력 크기 n은 배열 원소의 수, 알고리즘은 입력을 원하는 출력으로 바꾸는 명확한 절차다. 시간복잡도는 특정 컴퓨터에서 잰 초가 아니라 n이 커질 때 핵심 연산 수가 어떻게 늘어나는지를 나타낸다. Big-O는 그 증가율의 상한을 가장 크게 자라는 항으로 요약한다.
실행시간을 재면 생긴 의문
알고리즘 분석과 Big-O 노트에는 실험으로 시간을 재는 방법의 한계가 먼저 적혀 있다.
컴터 gpu & cpu가 좋을수록 실행시간이 다를 수 있으니까 실험적 방법 말고 이론적 방법 사용
실험에 포함되지 않은 입력에 대한 실행시간? 몰라!
같은 프로그램도 컴퓨터와 그날의 실행 환경에 따라 초 단위 결과는 달라진다. 더 큰 입력을 전부 실행해 볼 수도 없다. 그래서 관심을 “몇 초 걸렸는가”에서 “입력이 커질 때 일이 몇 번 늘어나는가”로 옮긴다.
저장소의 누적 평균 코드는 이 차이를 한 파일에 나란히 담고 있다. 첫 방법은 각 위치 i에서 arr[0]부터 arr[i]까지 다시 더한다. 전체 흐름을 줄이면 다음과 같다.
for (int i = 0; i < n; i++) {
sum = 0;
for (int j = 0; j <= i; j++) sum += arr[j];
prefix[i] = sum / (i + 1);
}
첫 평균에는 덧셈 1번, 다음에는 2번, 마지막에는 n번이 필요하다.
\[1+2+\cdots+n=\frac{n(n+1)}{2}\]가장 빠르게 커지는 항은 $n^2$이므로 전체는 $O(n^2)$이다. 반복문이 두 개라는 모양만 보고 판단한 것이 아니라, 실제 반복 횟수를 합한 결과다. 중첩 반복문이어도 안쪽 반복 횟수가 항상 작게 고정되어 있다면 $O(n)$일 수 있다.
저장소의 누적 평균 구현은 두 번째 방법에서 이전 평균을 이용한다.
next_average = (previous_average * (n - 1) + arr[n - 1]) / n;
앞에서 이미 계산한 합을 평균 형태로 보관했다가 새 원소 하나만 합친다. 각 위치에서 하는 일이 일정하므로 n개 결과를 만드는 비용은 $O(n)$이다.
증가율을 숫자로 확인하기
이번에 만든 연산 횟수 확인 코드는 두 누적 평균 알고리즘의 반복문을 실제로 실행하면서 덧셈 때마다 count를 늘린다. 검증 코드는 원본의 “이전 평균” 대신 누적합을 보관하는 동등한 선형 방식으로 작성했고, 각 위치의 평균이 오차 $10^{-12}$ 안에서 같은지도 검사했다.
| n | 매번 다시 합산 | 이전 결과 재사용 |
|---|---|---|
| 4 | 10 | 4 |
| 8 | 36 | 8 |
| 16 | 136 | 16 |
| 32 | 528 | 32 |
네 입력 크기 모두 averages_equal=true를 확인했다. 표의 횟수는 공식을 그대로 출력한 값이 아니라 실행한 덧셈에서 센 값이다.
n이 두 배가 될 때 선형 방식은 일이 두 배가 되고, 제곱 방식은 대략 네 배가 된다. 이 비율은 CPU가 바뀌어도 달라지지 않는다. 노트에서 원시 작업을 세려고 했던 이유가 여기에 있다.
다만 노트 끝의 “n²면 개량이 필요한 경우”는 조건을 붙여 읽어야 한다. n이 10이라면 단순한 제곱 알고리즘이 복잡한 선형 알고리즘보다 충분히 빠를 수 있다. 반대로 n이 백만까지 커진다면 증가율이 지배한다. Big-O는 실행시간표가 아니라 입력 크기가 커질 때의 상한을 단순화한 표현이다.
평균값 자체도 같은지 확인하기
두 번째 방식에는 별도 주의점도 있다. 이전 평균을 매 단계 정수로 반올림해 저장하면 잃어버린 소수 부분이 다음 계산에 다시 들어가지 못한다. 저장소 코드는 double avg를 유지하고 출력할 때만 반올림한다. 복잡도는 같아도 자료형과 반올림 시점에 따라 답은 달라질 수 있다.
이번 글에서 남은 기준은 세 가지다.
- 벽시계 시간보다 입력에 따른 연산 횟수를 먼저 본다.
- 반복문의 개수보다 각 반복이 실제로 몇 번 도는지 합한다.
- 같은 Big-O라도 계산 결과의 정확성과 상수 비용은 따로 검토한다.
“실행하지 않은 입력은 모른다”는 의문에 Big-O가 모든 답을 주지는 않는다. 대신 입력이 커질 때 감당할 수 없는 방식이 무엇인지, 실행 전에 걸러낼 기준을 준다.