점근 표기(Asymptotic notation)
직관 → 조작 → 예시 → 함정 → 답안
Asymptotic notation(Landau-Notation)은 실제 초 단위 시간이 아니라 입력 크기 n이 충분히 커졌을 때 Laufzeit이 어떤 성장급(Wachstumsklasse)에 속하는지 말하는 언어입니다. 작은 n에서의 우연한 교차, 상수배, 낮은 차수항을 버리고 dominant term을 찾은 뒤,...
O(g): 상한(upper bound / obere Schranke)\(\Omega(g): 하한(\text{lower} \text{bound} / \text{untere} \text{Schranke})\)Ω(g): 하한(lower bound / untere Schranke)\(\Theta(g): 긴밀한 경계(\text{tight} \text{bound} / \text{scharfe} \text{Schranke})\)Θ(g): 긴밀한 경계(tight bound / scharfe Schranke)o(g): 엄격하게 더 느린 성장(strictly smaller growth)c, c1, c2: 양의 상수 배수작은 입력의 소음은 버리고, n이 커질 때 누가 성장을 지배하는지 본다
점근 표기(asymptotic notation, Landau-Notation)는 알고리즘을 초시계로 한 번 재는 도구가 아니라 입력 크기(Eingabelänge) n이 충분히 커질 때 실행 시간(Laufzeit) 함수가 어떤 성장률(Wachstumsklasse)에 들어가는지 말하는 언어입니다. 시험에서는 먼저 지배항(dominant term)을 찾고, 문제의 부등식 방향에 맞게 Big-O, Big-Omega, Big-Theta, little-o 중 가장 제한적인 표기(restriktivste Notation)를 고르는 것이 핵심입니다.
먼저 알아야 할 개념 지도(Prerequisite Mini-Map)
함수 비교
f(n)과 g(n)은 양의 실행 시간(Laufzeit) 함수라고 생각합니다. 목표는 “어느 함수가 더 빨리 자라나?”입니다.
부등식 감각
Big-O는 \(f(n) \le c g(n)\)f(n) ≤ c g(n) 꼴의 천장, Big-Omega는 \(c g(n) \le f(n)\)c g(n) ≤ f(n) 꼴의 바닥입니다.
충분히 큰 n
정의는 항상 \(n \ge n_{0}\)n ≥ n₀ 이후만 봅니다. 초반에 그래프가 교차해도 점근적 성장급(Landau class)은 깨지지 않습니다.
강의 자료에 근거한 개념 지도
근거: \(\text{data}/\text{aud}_{\text{topi}}\,c_{\text{map}}.\text{md}\)data/aud(topic)(map).md는 Übung\AuD26_Sheet02.pdf와 Übung\AuD26_Sheet02-Sol.pdf를 “점근 표기와 실행 시간 분석(Asymptotic notation and runtime analysis)”으로 매핑합니다. \(\text{data}/\text{aud}_{\text{chunks}}.\text{jsonl}\)data/aud(chunks).jsonl 13~15행은 Sheet02 G2가 “상수와 합은 무시한다”, “구체적인 입력 하나의 실행 시간(Laufzeit)이 아니라 큰 입력 길이(Eingabelänge)에서의 성장 전개를 본다”는 문항을 포함하고, G4~G7이 O, o, Omega, Theta의 정의와 계산 규칙을 연습시킵니다. 강의 쪽은 주제 지도의 Vorlesung\02Sorting.pdf, Vorlesung\02Sorting_updated.pdf가 정렬(sorting), 점근 분석(asymptotic analysis), 분할 정복(divide and conquer) 범위로 연결됩니다.
자료의 한계(Source gap): 추출된 텍스트에는 슬라이드의 실제 그래프 배치가 완전하게 보존되어 있지 않습니다. 아래 경계(envelope) 그림은 Sheet02의 공식 정의와 큰 n 이후 비교 원리를 Study Hub용으로 재구성한 시각화입니다.
O, Omega, Theta는 “방향이 있는 부등식”으로 읽는다
Big-O: 위에서 누르는 상한 (upper bound)
f(n) ∈ O(g(n)) ⇔ ∃ c > 0, n₀: ∀ n ≥ n₀, 0 ≤ f(n) ≤ c g(n)충분히 큰 n 이후에는 f가 c*g 천장 위로 올라가지 못한다는 뜻입니다. O는 “최악의 경우”라는 말이 아니라 함수 사이의 상한(upper bound) 관계입니다.
Big-Omega: 아래에서 받치는 하한 (lower bound)
f(n) ∈ \Ω(g(n)) ⇔ ∃ c > 0, n₀: ∀ n ≥ n₀, 0 ≤ c g(n) ≤ f(n)충분히 큰 n 이후에는 f가 c*g 바닥 아래로 내려가지 않는다는 뜻입니다. Omega 역시 최선의 경우(best case)가 아니라 하한(lower bound)입니다.
Big-Theta: 위아래가 맞는 긴밀한 경계 (tight bound)
f(n) ∈ \Θ(g(n)) ⇔ ∃ c₁,c₂ > 0, n₀: ∀ n ≥ n₀, c₁ g(n) ≤ f(n) ≤ c₂ g(n)위와 아래가 동시에 맞는 긴밀한 경계(tight bound)입니다. 시험에서 “정확한 성장률”을 물으면 보통 Theta가 목표입니다.
little-o: 엄격하게 더 느린 성장 (strictly smaller)
f(n) ∈ o(g(n)) ⇔ limₙ→∞} f(n)/g(n) = 0f가 g보다 엄격하게 느리게 자랍니다. 예: \(n \log n\in o(n^{2})\)n log n ∈ o(n²).
경계선을 그림으로 읽기
상한: Big-O
\(n_{0}\)n₀이후 f는 c·g 아래에 있습니다.
하한: Big-Omega
\(n_{0}\)n₀이후 f는 c·g 위에 있습니다.
긴밀한 경계: Big-Theta
f가 두 상수배 사이에 끼이면 같은 성장률입니다.
단계별 풀이 예제
문제
\(f(n)=2n^{2}+3n+4\)f(n)=2n²+3n+4를 가능한 가장 제한적인 Landau notation으로 쓰세요.
풀이
- 항을 나눕니다: \(2n^{2}\)
2n²,3n,4. - n이 커질수록 가장 빨리 자라는 항은 \(n^{2}\)
n²입니다. - 상수
2는 성장률을 바꾸지 않습니다. 3n과4는 낮은 차수항(lower-order terms)입니다.
결론
\(f(n)\in \Theta(n^{2})\)f(n) ∈ Θ(n²). \(O(n^{3})\)O(n³)도 참이지만 너무 느슨해서 restriktivste Notation이 아닙니다.
성장률 순서 사다리 (Growth Ladder)
n²\(n^{3}\)n³\(a^{n}\)aⁿn!\(n^{n}\)nⁿ
오른쪽으로 갈수록 충분히 큰 n에서 더 빠르게 자랍니다. 여기서 \(a > 1\)a > 1은 고정 상수입니다. 로그의 밑은 상수배 차이만 만들기 때문에 같은 Landau class로 봅니다.
log_a n = log_b n / log_b a
따라서 \(a,b > 1\)a,b > 1이면 \(\log_{a} n \in \Theta(\log_{b} n)\)log_a n ∈ Θ(log_b n)
두 함수의 성장률 비교기
함수 두 개를 고르고 n을 움직여 보세요. 막대 높이는 실제 기계의 정확한 실행 시간이 아니라 상대적인 성장 속도를 나타냅니다.
n을 움직여 어떤 항이 결국 성장을 지배하는지 확인하세요.
객관식 함정과 바로잡기
O와 Theta 혼동
함정: \(n \log n\in O(n^{2})\)n log n ∈ O(n²)이므로 \(\Theta(n^{2})\)Θ(n²)도 맞다. 교정: O는 upper bound라서 참인 답이 많고, Theta는 양쪽 bound가 필요합니다.
Omega와 worst case 혼동
함정: Omega는 항상 worst-case Laufzeit이다. 교정: worst/best/average는 입력 경우의 말이고, Omega는 함수의 lower bound입니다.
\(n_{0}\)n₀이전에 집착
함정: 작은 n에서 그래프가 교차하면 bound가 틀린다. 교정: 정의는 \(n \ge n_{0}\)n ≥ n₀ 이후만 봅니다.
상수 무시를 현실 성능 무시로 오해
교정: Landau class에서는 100n과 n이 둘 다 \(\Theta(n)\)Θ(n)입니다. 실제 구현 성능에서는 상수가 여전히 중요할 수 있습니다.
중첩 loop 자동 \(n^{2}\)n²
교정: 안쪽 loop가 매번 두 배로 증가하면 반복 횟수는 \(\log n\)log n일 수 있어 전체가 \(\Theta(n \log n)\)Θ(n log n)이 됩니다.
한 방향만 보이고 Theta 결론
교정: \(f(n) \le c\cdot g(n)\)f(n) ≤ c*g(n)만 보이면 O입니다. Theta에는 lower bound도 필요합니다.
구두 답안과 능동 회상
- 먼저 Big-O, Big-Omega, Big-Theta를 부등식 방향까지 포함해서 정의해 보세요.
- \(2n^{2}+3n+4\)
2n²+3n+4가 왜 \(\Theta(n^{2})\)Θ(n²)인지 dominant term으로 설명하세요. - \(O(n^{3})\)
O(n³)도 참인데 왜 좋은 최종 답이 아닌지 말해 보세요. - Omega와 worst case가 다른 이유를 한 문장으로 구분하세요.
- \(\log_{2} n\)
log₂ n과 \(\log_{10} n\)log₁₀ n이 같은 Landau class인 이유를 공식으로 보이세요. - 새 문제: \(f(n)=7n \log n + 4n\)
f(n)=7n log n + 4n의 tight bound를 말하고, 왜 그런지 설명하세요.
추가 학습용 AI 프롬프트
Übung/AuD26_Sheet02.pdf, Übung/AuD26_Sheet02-Sol.pdf, Vorlesung/02Sorting.pdf, Vorlesung/02Sorting_updated.pdf를 첨부합니다. AUD 시험을 처음 준비하는 학생에게 점근 표기를 한국어로 가르쳐 주세요. 점근 표기(Landau notation), 성장률(Wachstum), 실행 시간(Laufzeit), 가장 제한적인 표기(restriktivste Notation), 상한(upper bound), 하한(lower bound), 긴밀한 경계(tight bound)는 함께 표시하세요. f(n)=2n^2+3n+4 → Theta(n^2)부터 시작해 O와 Theta의 차이, Omega와 최악의 경우(worst case)의 차이, 로그 밑의 동치, 성장률 사다리 비교, 중첩 반복문 함정을 한 번에 한 문제씩 연습시켜 주세요.출처 파일
- `Übung\AuD26_Sheet02.pdf`
- `Übung\AuD26_Sheet02-Sol.pdf`
- `Vorlesung\02Sorting.pdf`
- `Vorlesung\02Sorting_updated.pdf`
- `Vorlesung\02aSorting.pdf`
- `AuD Gedächtnisprotokoll SoSe 2025.md`
- `data\aud_chunks.jsonl`
연결 개념 (Related concepts)
후속 튜터 학습 프롬프트
마지막 생성: 2026-08-03 03:24