점근적 성장과 반복문 실행시간

점근 표기(asymptotic notation)는 작은 n의 실제 초수가 아니라 n이 충분히 커진 뒤 어떤 항이 성장을 지배하는지를 본다. O는 위에서 누르는 upper bound, Ω는 아래에서 받치는 lower bound, Θ는 둘 다 맞는 tight bound다. I-1의 성장 순서는 \(n \log n < n^{2} < n^{\log n} < 2^{n}. \text{II}-2\)n log n < n² < n^(log n) < 2ⁿ. II-2는 각 i에서 while이 \(\Theta(\log i)\)Θ(log i)번 돌기 때문에 전체가 \(\sum \log i = \Theta(n \log n)\)Σ log i = Θ(n log n)이고, 그래서 \(O(n^{2})\)O(n²)도 참이다.

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)이다.

보기의 'in \(O(...)\)O(...)'와 'in \(\Theta(...)\)Θ(...)'를 같은 말로 읽으면 틀린다. \(O(n^{2})\)O(n²)는 느슨한 upper bound로 참일 수 있지만 \(\Theta(n^{2})\)Θ(n²)는 tight해야 한다.

• I-1
• II-2

I부에서는 정답을 정확히 1개, II부에서는 정확히 2개 골라야 한다.

정답 순서를 외우는 것이 아니라 각 보기를 독립적인 true/false claim으로 바꾸고, O와 Θ의 의미를 분리해서 판단하게 한다.

시험 복기 자료(Gedächtnisprotokoll)는 문항 표현을 복원한 자료일 뿐 공식 정답지가 아니다. 각 판정은 현재 2026년 여름학기 강의와 연습문제 2(Sheet02)를 기준으로 확인했다.

현재 강의는 \(f \in O(g)\)f ∈ O(g)를 집합 포함 관계로 명시한다. 이 관례에서는 실행시간이 \(\Theta(n \log n)\)Θ(n log n)일 때 \(O(n^{2})\)O(n²)도 느슨한 상한(upper bound)으로 참이다.

점근 분석은 알고리즘의 속도를 작은 입력에서 실험한 값으로 재는 것이 아니라, 입력 크기 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를 뜻한다.

• \(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)²)로 바꿔 쓸 수 있다.

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)다.

전체 실행시간은 \(\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)이다.

로그 밑이 고정 상수이면 Θ-class는 바뀌지 않는다. \(n^{\log n}\)n^(log n)은 모든 고정 차수 다항식보다 빠르게 자라지만 \(2^{n}\)2ⁿ같은 고정 밑 지수함수보다는 느리다. 작은 n에서 우연히 값이 뒤집혀도 점근 비교는 충분히 큰 n 이후만 본다.

• genau eine
• genau zwei
• in O
• \(\text{in} \Theta\)in Θ
• restriktivste Notation
• konstante Faktoren
• Eingabelänge
• worst case
• \(\text{while} j < i\)while j < i
• \(j = 2 \cdot j\)j = 2 * j

O는 위, Ω는 아래, Θ는 양쪽. O가 참이라고 tight하다는 뜻은 아니다.

II-2에서는 각 i마다 while 반복 횟수가 \(\Theta(\log i)\)Θ(log i)이고, 전체 합은 \(\Theta(n \log n)\)Θ(n log n)이다. 따라서 \(O(n^{2})\)O(n²)와 \(\Theta(n \log n)\)Θ(n log n)이 모두 참이다.

작은 n의 값은 점근 판정에서 결정적이지 않다. log base is fixed라는 조건은 비율이 상수배라는 뜻이다.

성장 순서는 ladder로, loop runtime은 합으로, MC 보기는 독립 true/false로 처리한다.