II-2 두 배씩 증가하는 중첩 반복문의 실행시간 — 완전 초보자 Masterclass
먼저 이 문제의 정체부터
중첩 loop라고 무조건 \(n^{2}\)n²가 아닙니다. 안쪽 j가 1씩 증가하는지 두 배가 되는지를 먼저 봅니다. 1,2,4,8,…은 i에 도달하는 데 \(\log_{2}i\)log₂i번만 필요합니다.
한 계단씩 걷는 것이 아니라 매번 이동 거리가 두 배가 되는 순간이동입니다.
이 문항의 풀이 목표는 정답 label 암기가 아니라 다음 절차를 재현하는 것입니다. inner count를 log i로 바꾼 뒤 outer 합을 계산하고, O와 Θ를 별도로 판단합니다.
복기 시험지는 공식 답안지가 아니므로 문언과 selection rule이 충돌하면 그 사실을 표시하고 현재 강의 자료로 각 보기를 독립 검증합니다.
0. 필요한 개념을 처음부터 배우기
개념 1 · 문제의 정체를 생활 언어로
중첩 loop라고 무조건 \(n^{2}\)n²가 아닙니다. 안쪽 j가 1씩 증가하는지 두 배가 되는지를 먼저 봅니다. 1,2,4,8,…은 i에 도달하는 데 \(\log_{2}i\)log₂i번만 필요합니다.
이 문항에서 가장 먼저 붙잡을 문장은 'k번 갱신 뒤 \(j=2^{k}\)j=2ᵏ이다.'입니다. 용어를 외우기 전에 이 문장이 어떤 상황을 말하는지 작은 예를 만들어 확인합니다.
이 절에서 꼭 기억할 것
- k번 갱신 뒤 \(j=2^{k}\)
j=2ᵏ이다. - inner count를 log i로 바꾼 뒤 outer 합을 계산하고, O와 Θ를 별도로 판단합니다.
개념 2 · 반드시 알아야 하는 네 개의 뼈대
첫째, k번 갱신 뒤 \(j=2^{k}\)j=2ᵏ이다. 둘째, 고정 i에서 while 횟수는 \(\Theta(\log i)\)Θ(log i)이다.
셋째, 전체 합 \(\sumlog i=\log(n!)=\Theta(n \log n)\)Σlog i=log(n!)=Θ(n log n)이다. 넷째, \(\Theta(n \log n)\)Θ(n log n)이면 더 느슨한 \(O(n^{2})\)O(n²)도 참이지만 \(\Theta(n^{2})\)Θ(n²)는 거짓이다. 이 네 문장을 서로 섞지 않고 별도 체크박스로 기억해야 합니다.
이 절에서 꼭 기억할 것
- k번 갱신 뒤 \(j=2^{k}\)
j=2ᵏ이다. - 고정 i에서 while 횟수는 \(\Theta(\log i)\)
Θ(log i)이다. - 전체 합 \(\sumlog i=\log(n!)=\Theta(n \log n)\)
Σlog i=log(n!)=Θ(n log n)이다. - \(\Theta(n \log n)\)
Θ(n log n)이면 더 느슨한 \(O(n^{2})\)O(n²)도 참이지만 \(\Theta(n^{2})\)Θ(n²)는 거짓이다.
개념 3 · 강의 정의를 초보자 언어로 해체
점근 분석은 알고리즘의 속도를 작은 입력에서 실험한 값으로 재는 것이 아니라, 입력 크기 n이 커질수록 어떤 항이 결국 지배하는지를 보는 언어다. 예를 들어 \(2n^{2}+3n+4\)2n²+3n+4에서는 \(n^{2}\)n²항이 지배하고 상수 2, 낮은 차수 3n, 상수항 4는 성장급을 바꾸지 않는다. 따라서 가장 제한적인 표기(restriktivste Notation)는 \(\Theta(n^{2})\)Θ(n²)다. 반대로 \(O(n^{3})\)O(n³)도 참이지만 시험에서 tight한 답을 묻는 상황에서는 너무 느슨하다.
\(f \in O(g)\)f ∈ O(g)는 충분히 큰 n에서 \(f(n) \le c g(n)\)f(n) ≤ c g(n)가 되는 upper bound다. \(f \in \Omega(g)\)f ∈ Ω(g)는 충분히 큰 n에서 \(c g(n) \le f(n)\)c g(n) ≤ f(n)가 되는 lower bound다. \(f \in \Theta(g)\)f ∈ Θ(g)는 두 조건이 동시에 성립하는 tight bound다. little-o는 \(f(n)/g(n) \to 0\)f(n)/g(n) → 0인 strictly smaller growth를 뜻한다.
수식으로 정확히 쓰기
핵심 규칙k가 고정 상수이고 \(c>1\)c>1일 때 성장 순서는 \(\log n < n < n \log n < n^{2} < n^{k} < n^{\log n} < c^{n}\)log n < n < n log n < n² < nᵏ < n^(log n) < cⁿ이다. 또한 \(\sum_{i=1}^n \log i = \log(n!) = \Theta(n \log n)\)Σ[i=1]ⁿ log i = log(n!) = Θ(n log n)이다.
이 절에서 꼭 기억할 것
- \(a,b>1\)
a,b>1이 고정된 로그 밑이면 \(\log_{a} n = \Theta(\log_{b} n)\)log_a n = Θ(log_b n)이다. - \(\Theta(g)\)
Θ(g)는 \(O(g)\)O(g)와 \(\Omega(g)\)Ω(g)의 교집합이다:\(\Theta(g) = O(g) ∩ \Omega(g).\)Θ(g) = O(g) ∩ Ω(g). - \(f \in O(g)\)
f ∈ O(g)라는 사실만으로는 \(f \in \Theta(g)\)f ∈ Θ(g)를 결론낼 수 없다. - 로그 밑이 2일 때 \(n^{\log n} = 2^{(\log_{2} n)^{2}}\)
n^(log n) = 2^((log₂ n)²)로 바꿔 쓸 수 있다.
개념 4 · 성립 조건·불변식·경계 사례
II-2의 while loop에서 k번 update한 뒤에는 \(j=2^{k}\)j=2ᵏ다. \(j<i\)j<i조건이 깨지는 최초 k는 \(\text{ceil}(\log_{2} i)\)ceil(log₂ i)근처이므로 i번째 outer iteration의 inner iteration 수는 \(\Theta(\log i)\)Θ(log i)다.
로그 밑이 고정 상수이면 Θ-class는 바뀌지 않는다. \(n^{\log n}\)n^(log n)은 모든 고정 차수 다항식보다 빠르게 자라지만 \(2^{n}\)2ⁿ같은 고정 밑 지수함수보다는 느리다. 작은 n에서 우연히 값이 뒤집혀도 점근 비교는 충분히 큰 n 이후만 본다.
이 절에서 꼭 기억할 것
- 전제조건을 생략하지 않는다.
- 존재 명제와 모든 경우 명제를 구분한다.
- 강한 단어는 작은 반례로 우선 검사한다.
개념 5 · 실행시간과 비용을 읽는 법
전체 실행시간은 \(\sum_{i=1}^n \Theta(\log i) = \Theta(\log(n!)) = \Theta(n \log n)\)Σ[i=1]ⁿ Θ(log i) = Θ(log(n!)) = Θ(n log n)이다. 따라서 \(f(n) \in O(n^{2})\)f(n) ∈ O(n²)와 \(f(n) \in \Theta(n \log n)\)f(n) ∈ Θ(n log n)은 참이고, \(f(n) \in O(n)\)f(n) ∈ O(n)과 \(f(n) \in \Theta(n^{2})\)f(n) ∈ Θ(n²)는 거짓이다. 변수 c, i, j만 보면 추가 공간은 \(O(1)\)O(1)이다.
O는 upper bound이고 Θ는 tight bound입니다. 자료구조 연산 비용은 ADT 이름만이 아니라 구현과 유지하는 보조 정보에 따라 달라질 수 있습니다.
이 절에서 꼭 기억할 것
- O와 Θ를 같은 뜻으로 읽지 않는다.
- 구현 의존성을 확인한다.
- 필요 없는 runtime 주장도 억지로 만들지 않는다.
개념 6 · 정확히 두 개 선택(exactly two) 판정법
선택지를 서로 비교해 '가장 그럴듯한 두 개'를 고르지 않습니다. A부터 D까지 각각 독립적인 참·거짓 명제로 바꾸고 근거 또는 반례를 붙인 뒤 참의 개수를 셉니다.
현재 복기 데이터에서 판정된 정답 표시는 B, C입니다. 정답 수와 섹션 규칙이 충돌하는 문항은 억지로 두 개를 만들지 않고 복기 문언 누락 가능성을 명시합니다.
수식으로 정확히 쓰기
핵심 규칙선택 규칙: 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
핵심 규칙검증된 선택지: B, C
이 절에서 꼭 기억할 것
- 중첩 loop라서 \(\Theta(n^{2})\)
Θ(n²)라고 찍는 함정과, \(O(n^{2})\)O(n²)가 참이면 \(\Theta(n^{2})\)Θ(n²)도 참이라고 착각하는 함정이 동시에 있다. - j가 매번 두 배가 되면 log, outer loop가 n번이면 n log n. 그 다음 \(O(n^{2})\)
O(n²)는 upper bound라서 참인지 따로 확인한다.
1. 시험장에서 따라 할 풀이 순서
선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
두 배씩 증가하는 중첩 반복문의 실행시간
k번 갱신 뒤 \(j=2^{k}\)j=2ᵏ이다. | 고정 i에서 while 횟수는 \(\Theta(\log i)\)Θ(log i)이다. | 전체 합 \(\sumlog i=\log(n!)=\Theta(n \log n)\)Σlog i=log(n!)=Θ(n log n)이다.
선택지 \(A =\)A =거짓
선택 규칙을 먼저 적는다
이 문항의 규칙은 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))입니다. 마지막에 참 개수를 반드시 재검산합니다.핵심 규칙선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))문장을 쉬운 한국어로 다시 쓴다
f를 다음 알고리즘 Alg(n)의 실행시간이라고 하자: \(c=0\)
c=0; \(i=1\)i=1부터 n까지 반복하고, 매번 \(j=1\)j=1에서 시작하여 \(j<i\)j<i동안 j를 2*j로 바꾸고 c에 j를 더한다.핵심 규칙두 배씩 증가하는 중첩 반복문의 실행시간
핵심 도구를 종이에 꺼낸다
inner count를 log i로 바꾼 뒤 outer 합을 계산하고, O와 Θ를 별도로 판단합니다.
핵심 규칙k번 갱신 뒤 \(j=2^{k}\)
j=2ᵏ이다. | 고정 i에서 while 횟수는 \(\Theta(\log i)\)Θ(log i)이다. | 전체 합 \(\sumlog i=\log(n!)=\Theta(n \log n)\)Σlog i=log(n!)=Θ(n log n)이다.선택지 A를 독립 판정한다
각 i마다 while이 \(\Theta(\log i)\)
Θ(log i)번 돈다. 전체 합은 \(\Theta(n \log n)\)Θ(n log n)이므로 \(O(n)\)O(n)이 아니다.\[선택지 A = 거짓\]선택지 A = 거짓선택지 B를 독립 판정한다
tight bound는 \(\Theta(n \log n)\)
Θ(n log n)이지만 \(n \log n \in O(n^{2})\)n log n ∈ O(n²)이므로 \(O(n^{2})\)O(n²)는 참이다. O는 정확한 성장률만 적는 표기가 아니라 upper-bound 집합이다.\[선택지 B = 참\]선택지 B = 참선택지 C를 독립 판정한다
i번째 while 반복 횟수는 \(\Theta(\log i)\)
Θ(log i)이고, 총합은 \(\sum \log i = \log(n!) = \Theta(n \log n)\)Σ log i = log(n!) = Θ(n log n)이다.\[선택지 C = 참\]선택지 C = 참선택지 D를 독립 판정한다
inner loop는 i번이 아니라 log i번만 돈다. 따라서 tight bound는 \(\Theta(n \log n)\)
Θ(n log n)이고, n log n은 \(n^{2}\)n²보다 점근적으로 작다.\[선택지 D = 거짓\]선택지 D = 거짓정답 수와 애매성을 재검산한다
참으로 판정된 선택지는 B, C입니다. 복기 섹션 규칙과 수가 다르면 원문 누락 가능성을 기록하고 거짓을 참으로 조작하지 않습니다.
\[검증된 정답 = B, C\]검증된 정답 = B, C
2. 이 문제를 실제로 끝까지 풀기
중첩 loop라고 무조건 \(n^{2}\)n²가 아닙니다. 안쪽 j가 1씩 증가하는지 두 배가 되는지를 먼저 봅니다. 1,2,4,8,…은 i에 도달하는 데 \(\log_{2}i\)log₂i번만 필요합니다.
풀이를 시작할 때 다음 네 사실을 먼저 적습니다. (1) k번 갱신 뒤 \(j=2^{k}\)j=2ᵏ이다. (2) 고정 i에서 while 횟수는 \(\Theta(\log i)\)Θ(log i)이다. (3) 전체 합 \(\sumlog i=\log(n!)=\Theta(n \log n)\)Σlog i=log(n!)=Θ(n log n)이다. (4) \(\Theta(n \log n)\)Θ(n log n)이면 더 느슨한 \(O(n^{2})\)O(n²)도 참이지만 \(\Theta(n^{2})\)Θ(n²)는 거짓이다.
선택지 A는 거짓입니다. 각 i마다 while이 \(\Theta(\log i)\)Θ(log i)번 돈다. 전체 합은 \(\Theta(n \log n)\)Θ(n log n)이므로 \(O(n)\)O(n)이 아니다. 가장 작은 확인 예는 \(i \ge n/2\)i ≥ n/2인 outer iterations가 n/2개 있고, 각각 \(\Omega(\log n)\)Ω(log n)번 while을 돈다. 따라서 전체가 \(\Omega(n \log n)\)Ω(n log n)이다.
선택지 B는 참입니다. tight bound는 \(\Theta(n \log n)\)Θ(n log n)이지만 \(n \log n \in O(n^{2})\)n log n ∈ O(n²)이므로 \(O(n^{2})\)O(n²)는 참이다. O는 정확한 성장률만 적는 표기가 아니라 upper-bound 집합이다.
선택지 C는 참입니다. i번째 while 반복 횟수는 \(\Theta(\log i)\)Θ(log i)이고, 총합은 \(\sum \log i = \log(n!) = \Theta(n \log n)\)Σ log i = log(n!) = Θ(n log n)이다.
선택지 D는 거짓입니다. inner loop는 i번이 아니라 log i번만 돈다. 따라서 tight bound는 \(\Theta(n \log n)\)Θ(n log n)이고, n log n은 \(n^{2}\)n²보다 점근적으로 작다. 가장 작은 확인 예는 \(f(n)/n^{2} = \Theta((n \log n)/n^{2}) = \Theta(\log n/n) \to 0\)f(n)/n² = Θ((n log n)/n²) = Θ(log n/n) → 0이므로 quadratic lower bound가 없다.
따라서 현재 문언에서 참으로 검증된 선택지는 B, C입니다. 선택지는 서로 상대평가하지 않고 각 문장을 정의·전제·반례로 독립 검증했습니다.
시험장에서 쓸 압축 절차는 다음과 같습니다. inner count를 log i로 바꾼 뒤 outer 합을 계산하고, O와 Θ를 별도로 판단합니다. 시간이 부족해도 '항상(always)', '오직(only)', '모든(every)' 같은 강한 단어와 전제조건, O와 Θ를 먼저 확인하면 대표 함정을 피할 수 있습니다.
3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기
-
A거짓
각 i마다 while이 \(\Theta(\log i)\)
Θ(log i)번 돈다. 전체 합은 \(\Theta(n \log n)\)Θ(n log n)이므로 \(O(n)\)O(n)이 아니다.빠른 확인법: \(i \ge n/2\)
i ≥ n/2인 outer iterations가 n/2개 있고, 각각 \(\Omega(\log n)\)Ω(log n)번 while을 돈다. 따라서 전체가 \(\Omega(n \log n)\)Ω(n log n)이다. -
B참 — 정답 후보
tight bound는 \(\Theta(n \log n)\)
Θ(n log n)이지만 \(n \log n \in O(n^{2})\)n log n ∈ O(n²)이므로 \(O(n^{2})\)O(n²)는 참이다. O는 정확한 성장률만 적는 표기가 아니라 upper-bound 집합이다.빠른 확인법: f(n)은 \(O(n^{2})\)
O(n²)에 속한다. -
C참 — 정답 후보
i번째 while 반복 횟수는 \(\Theta(\log i)\)
Θ(log i)이고, 총합은 \(\sum \log i = \log(n!) = \Theta(n \log n)\)Σ log i = log(n!) = Θ(n log n)이다.빠른 확인법: f(n)은 \(\Theta(n \log n)\)
Θ(n log n)에 속한다. -
D거짓
inner loop는 i번이 아니라 log i번만 돈다. 따라서 tight bound는 \(\Theta(n \log n)\)
Θ(n log n)이고, n log n은 \(n^{2}\)n²보다 점근적으로 작다.빠른 확인법: \(f(n)/n^{2} = \Theta((n \log n)/n^{2}) = \Theta(\log n/n) \to 0\)
f(n)/n² = Θ((n log n)/n²) = Θ(log n/n) → 0이므로 quadratic lower bound가 없다.
4. 초보자가 가장 자주 틀리는 이유
- 중첩 loop라서 \(\Theta(n^{2})\)
Θ(n²)라고 찍는 함정과, \(O(n^{2})\)O(n²)가 참이면 \(\Theta(n^{2})\)Θ(n²)도 참이라고 착각하는 함정이 동시에 있다. - exactly-two라는 이유만으로 근거 없이 두 선택지를 맞다고 만든다.
- 선택지의 절반만 맞는데 결합 문장 전체를 참으로 판정한다.
- always, only, every 같은 강한 단어를 놓친다.
- 정의와 구현, 전제조건과 결론, upper bound와 tight bound를 섞는다.
- 작은 예 하나로 거짓은 깰 수 있지만 참인 보편 명제를 증명했다고 착각한다.
- 복기 시험지가 공식 원문·공식 답안이라는 전제로 애매성을 숨긴다.
- 용어를 암기한 소리만 따라가고 실제 상태나 한 단계 실행을 그리지 않는다.
5. 시험 답안 템플릿
inner count를 log i로 바꾼 뒤 outer 합을 계산하고, O와 Θ를 별도로 판단합니다. 각 선택지를 정의와 전제에 따라 독립 판정하면 참인 label은 B, C이다. 핵심 근거: k번 갱신 뒤 \(j=2^{k}\)j=2ᵏ이다. 고정 i에서 while 횟수는 \(\Theta(\log i)\)Θ(log i)이다. 전체 합 \(\sumlog i=\log(n!)=\Theta(n \log n)\)Σlog i=log(n!)=Θ(n log n)이다. \(\Theta(n \log n)\)Θ(n log n)이면 더 느슨한 \(O(n^{2})\)O(n²)도 참이지만 \(\Theta(n^{2})\)Θ(n²)는 거짓이다.
6. 스스로 이해했는지 확인
II-2의 주제를 한 문장으로 설명하면?
정답: 중첩 loop라고 무조건 \(n^{2}\)n²가 아닙니다. 안쪽 j가 1씩 증가하는지 두 배가 되는지를 먼저 봅니다. 1,2,4,8,…은 i에 도달하는 데 \(\log_{2}i\)log₂i번만 필요합니다.
이 문제에서 가장 먼저 꺼낼 판정법은?
정답: inner count를 log i로 바꾼 뒤 outer 합을 계산하고, O와 Θ를 별도로 판단합니다.
핵심 사실 네 가지 중 첫 번째는?
정답: k번 갱신 뒤 \(j=2^{k}\)j=2ᵏ이다.
핵심 사실 네 가지 중 두 번째는?
정답: 고정 i에서 while 횟수는 \(\Theta(\log i)\)Θ(log i)이다.
가장 위험한 함정은?
정답: 중첩 loop라서 \(\Theta(n^{2})\)Θ(n²)라고 찍는 함정과, \(O(n^{2})\)O(n²)가 참이면 \(\Theta(n^{2})\)Θ(n²)도 참이라고 착각하는 함정이 동시에 있다.
정답 label은?
정답: B, C
\(O(g)\)O(g), \(\Omega(g)\)Ω(g), \(\Theta(g)\)Θ(g)를 각각 한 문장으로 말하라.
정답: O는 충분히 큰 n에서의 upper bound, Ω는 lower bound, Θ는 두 방향이 동시에 맞는 tight bound다.
왜 \(n \log n \in O(n^{2})\)n log n ∈ O(n²)이지만 n log n ∉ \(\Theta(n^{2})\)Θ(n²)인가.
정답: \(\log n \le n\)log n ≤ n이라 upper bound는 맞지만, \((n \log n)/n^{2} = \log n/n \to 0\)(n log n)/n² = log n/n → 0이라 quadratic lower bound가 없다.
근거 자료
AuD Gedächtnisprotokoll SoSe 2025.md· Multiple Choice II-2
복기된 문언과 선택지; 공식 답안지가 아님AuD Gedächtnisprotokoll SoSe 2025.md· Multiple Choice I.1 and II.2
SoSe 2025 복기 문항 I-1과 II-2의 문제 문장, 선택지, 섹션 규칙, 의사코드를 뒷받침한다.Vorlesung\02Sorting_updated.pdf· pp. 25-30; data/aud_chunks.jsonl lines 196-197
실행시간 분석은 입력 크기의 함수로 실제 실행 단계 수를 세며, 일반적인 계산 모델에서는 기본 연산을 상수 시간으로 취급한다는 내용을 뒷받침한다.Vorlesung\02Sorting_updated.pdf· pp. 31-41; data/aud_chunks.jsonl lines 198-201
지배항으로 식을 단순화하는 방법과 상수 및 n0를 사용한 Θ, O, Ω의 형식적 정의를 뒷받침한다.Vorlesung\02Sorting_updated.pdf· pp. 46-49; data/aud_chunks.jsonl lines 203-204
O와 Ω는 각각 상한과 하한의 집합이고, \(\Theta(g)\)Θ(g)는 \(O(g)\)O(g)와 \(\Omega(g)\)Ω(g)가 모두 성립할 때 정확히 성립하며, 더 느슨한 O 상한도 참일 수 있다는 내용을 뒷받침한다.