I-1 성장률 순서 — 식을 보자마자 계급표에 꽂는 법
먼저 이 문제의 정체부터
이 문제는 네 함수의 실제 실행시간을 계산하는 문제가 아닙니다. n이 아주 커질 때 어느 함수가 더 빨리 커지는지를 비교하는 문제입니다. 작은 n에서 값이 잠깐 뒤집히는지는 중요하지 않고, 충분히 큰 n 이후의 장기적인 성장 속도만 봅니다.
초보자가 가장 낯설어하는 항은 \(n^{\log n}\)n^(log n)입니다. 겉모습은 n의 거듭제곱이라 다항식처럼 보이지만 지수 log n이 고정 숫자가 아니라 n과 함께 계속 커집니다. 따라서 \(n^{2}\)n²같은 고정 차수 다항식보다 빠릅니다. 그렇다고 \(2^{n}\)2ⁿ처럼 지수가 n인 함수만큼 빠르지는 않습니다.
목표는 정답 B를 외우는 것이 아닙니다. 네 함수를 성장률 계급에 분류하고, 서로 이웃한 두 항의 순서를 한 줄씩 증명하는 습관을 만드는 것입니다. 그러면 숫자나 로그 밑이 바뀐 변형 문제에도 그대로 대응할 수 있습니다.
0. 필요한 개념을 처음부터 배우기
개념 1 · 점근 비교(asymptotischer Vergleich)는 무엇인가
입력 크기 n이 커질수록 필요한 연산 수가 어떻게 늘어나는지를 함수로 나타냅니다. 예를 들어 n log n과 \(n^{2}\)n²를 비교할 때 특정 컴퓨터에서 몇 초가 걸리는지는 묻지 않습니다. 비율 \((n \log n)/n^{2} = (\log n)/n\)(n log n)/n² = (log n)/n이 0으로 가므로 n log n이 \(n^{2}\)n²보다 점근적으로 느리게 성장한다고 말합니다.
문제의 '<'는 보통 숫자의 한 시점 비교가 아니라 '왼쪽 함수가 오른쪽 함수보다 엄밀히 낮은 성장급'이라는 뜻입니다. 가장 안전한 판정법은 두 함수의 비율을 보고 0이면 왼쪽이 느리고, 양의 상수면 같은 Θ-class이며, 무한대로 가면 왼쪽이 빠르다고 읽는 것입니다.
수식으로 정확히 쓰기
f=o(g) ⇔ lim(n→∞) f(n)/g(n)=0핵심 규칙상수배와 낮은 차수 항은 Θ-class를 바꾸지 않는다
이 절에서 꼭 기억할 것
- 작은 n의 표는 직관 확인용이지 증명 자체가 아니다.
- 로그 밑이 2, 10, e처럼 고정되어 있으면 상수배 차이뿐이다.
개념 2 · 성장률 계급표
시험에서는 함수 하나하나를 처음부터 미분할 필요가 없습니다. 자주 나오는 계급은 \(\text{logarithmic} < \text{linear} < n \log n < \text{fixed}-\text{degree} \text{polynomial} < \text{quasipolynomial} < \text{fixed}-\text{base} \text{exponential} < \text{factorial}\)logarithmic < linear < n log n < fixed-degree polynomial < quasipolynomial < fixed-base exponential < factorial순서입니다.
여기서 fixed-degree polynomial은 \(n^{2}, n^{7}\)n², n⁷처럼 지수가 고정된 함수입니다. quasipolynomial의 대표가 \(n^{\log n}\)n^(log n)입니다. fixed-base exponential은 \(2^{n}, 3^{n}\)2ⁿ, 3ⁿ처럼 밑은 고정이고 지수가 n에 비례하는 함수입니다.
수식으로 정확히 쓰기
핵심 규칙\(\log n < n < n \log n < n^{k} < n^{\log n} < c^{n} (k\)log n < n < n log n < nᵏ < n^(log n) < cⁿ (k와 \(c>1\)c>1은 고정 상수)
이 절에서 꼭 기억할 것
- n log n은 \(n^{2}\)
n²보다 작다. - \(n^{\log n}\)
n^(log n)은 모든 고정 차수 \(n^{k}\)nᵏ를 언젠가 추월한다. - \(2^{n}\)
2ⁿ은 \(n^{\log n}\)n^(log n)을 언젠가 추월한다.
개념 3 · \(n^{\log n}\)n^(log n)이 \(n^{2}\)n²보다 큰 이유
밑이 같은 n인 두 거듭제곱 \(n^{2}\)n²와 \(n^{\log n}\)n^(log n)을 비교하면 지수만 보면 됩니다. 2는 고정되어 있지만 log n은 매우 천천히라도 끝없이 증가합니다. 충분히 큰 n에서는 \(\log n>2\)log n>2이므로 \(n^{\log n}>n^{2}\)n^(log n)>n²입니다.
log의 밑이 2라면 \(n>4\)n>4부터 \(\log_{2} n>2\)log₂ n>2입니다. 밑이 10이라도 \(n>100\)n>100부터 \(\log_{10} n>2\)log₁₀ n>2입니다. 시작점만 달라질 뿐 '충분히 큰 n'에서는 결론이 같습니다.
수식으로 정확히 쓰기
핵심 규칙충분히 큰 n에서 log \(n > 2\)n > 2 ⇒ \(n^{\log n} > n^{2}\)n^(log n) > n²
핵심 규칙고정된 모든 k에 대해 충분히 큰 n에서는 \(\log n > k\)log n > k
이 절에서 꼭 기억할 것
- log n을 상수처럼 취급하지 않는다.
- 점근 비교에서는 '언젠가부터'가 핵심이다.
개념 4 · \(n^{\log n}\)n^(log n)이 \(2^{n}\)2ⁿ보다 작은 이유
밑이 서로 달라 바로 비교하기 어렵다면 둘 다 밑 2의 거듭제곱으로 바꿉니다. 바로 아래 첫 번째 표시 수식은 이 변환을 한 줄씩 정리한 것입니다.
두 식을 밑 2로 통일하면 지수만 비교하면 됩니다. 로그의 제곱은 n보다 훨씬 느리게 자라므로, 두 번째 표시 수식처럼 준다항식은 고정 밑 지수함수보다 느립니다. 로그의 밑이 달라도 지수에 상수배가 붙을 뿐이라 결론은 같습니다.
수식으로 정확히 쓰기
n^(log₂ n)=2^((log₂ n)²)(log n)²=o(n) ⇒ 2^((log n)²)=o(2ⁿ)이 절에서 꼭 기억할 것
- \(n^{\log n}\)
n^(log n)을 \(2^{...}\)2^(...)꼴로 바꾸는 것이 핵심 기술이다. - 지수가 \(\log^{2}n\)
log²n인 함수와 지수가 n인 함수는 큰 차이가 난다.
개념 5 · 숫자 대입은 언제 쓰는가
숫자 대입은 선택지를 빠르게 깨는 반례로 유용하지만 유한한 몇 값만으로 점근 명제를 완전히 증명하지는 못합니다. 예를 들어 \(\log_{2}\)log₂기준 \(n=8\)n=8이면 \(n \log n=24, n^{2}=64, n^{\log n}=512, 2^{n}=256\)n log n=24, n²=64, n^(log n)=512, 2ⁿ=256이라 마지막 두 항이 아직 최종 순서와 반대입니다.
\(n=32\)n=32에서는 \(n^{\log n}=2^{25}\)n^(log n)=2²⁵이고 \(2^{n}=2^{32}\)2ⁿ=2³²라서 최종 순서가 드러납니다. 이 변화가 바로 '충분히 큰 n 이후'라는 점근 개념을 보여 줍니다. 시험에서는 계급표와 식 변환으로 증명하고, 숫자는 직관 또는 오답 반례로만 보조합니다.
수식으로 정확히 쓰기
\(n=32\)n=32
n^(log₂n)=32⁵=2²⁵ < 2³²이 절에서 꼭 기억할 것
- 작은 n에서 순서가 달라도 점근 결론과 모순이 아니다.
- 반례는 universal claim을 깨는 데 쓰고, 최종 성장 순서는 일반식으로 정당화한다.
1. 시험장에서 따라 할 풀이 순서
목표: \(\text{slowest} \to \text{fastest}\)slowest → fastest
성장률 후보:\(n \log n\;\longrightarrow\;n^{2}\;\longrightarrow\;n^{\log n}\;\longrightarrow\;2^{n}\)n log n | n² | n^(log n) | 2ⁿ
f1과 \(f_{2}\)f2를 비교한다\(f_{1}=o(f_{2})\)f1=o(f2)
f2와 \(f_{4}\)f4를 비교한다충분히 큰 n에서 2<log n ⇒ \(f_{2}<f_{4}\)f2<f4
문제의 동사를 번역한다
'nach wachsender Komplexität'는 성장률이 낮은 것부터 높은 것으로 배열하라는 뜻입니다. 정확히 하나의 순서만 선택합니다.
핵심 규칙목표: \(\text{slowest} \to \text{fastest}\)
slowest → fastest네 함수를 체급에 분류한다
\(f_{1}\)
f1은 n log n, \(f_{2}\)f2는 2차 다항식, \(f_{4}\)f4는 준다항식, \(f_{3}\)f3은 고정 밑 지수함수입니다.성장률 후보
\[n \log n\;\longrightarrow\;n^{2}\;\longrightarrow\;n^{\log n}\;\longrightarrow\;2^{n}\]n log n | n² | n^(log n) | 2ⁿ\(f_{1}\)
f1과 \(f_{2}\)f2를 비교한다비율 \((n \log n)/n^{2}=\log n/n\)
(n log n)/n²=log n/n이 0으로 가므로 \(f_{1}\)f1이 더 느립니다.\[f_{1}=o(f_{2})\]f1=o(f2)\(f_{2}\)
f2와 \(f_{4}\)f4를 비교한다충분히 큰 n에서는 \(\log n>2\)
log n>2이므로 같은 밑 n에서 지수가 더 큰 \(f_{4}\)f4가 더 큽니다.핵심 규칙충분히 큰 n에서 2<log n ⇒ \(f_{2}<f_{4}\)
f2<f4\(f_{4}\)
f4와 \(f_{3}\)f3를 같은 밑으로 바꾼다\(f_{4}=2^{(\log_{2}n)^{2}}, f_{3}=2^{n}\)
f4=2^((log₂n)²), f3=2ⁿ으로 쓰면 \((\log n)^{2}<n \text{eventually}\)(log n)²<n eventually이므로 \(f_{4}\)f4가 더 느립니다.\[f_{4}=2^{\log^{2}n}<2^{n}=f_{3}\]f4=2^(log²n)<2ⁿ=f3완성된 사슬을 적는다
부분 비교 세 개를 이어 붙이면 \(f_{1}<f_{2}<f_{4}<f_{3}\)
f1<f2<f4<f3입니다.\[f_{1} < f_{2} < f_{4} < f_{3}\]f1 < f2 < f4 < f3선택지와 정확히 대조한다
사슬과 한 글자도 다르지 않은 선택지는 B입니다. 눈으로 대충 보지 말고 네 위치를 모두 확인합니다.
핵심 규칙정답 B
마지막 조건을 점검한다
log의 밑은 1보다 큰 고정 상수이고, '<'는 충분히 큰 n에서의 성장률 비교라는 조건을 확인합니다.
핵심 규칙로그의 밑은 고정 · 점근적 성장률 비교
2. 이 문제를 실제로 끝까지 풀기
첫 번째 비교는 \(f_{1}=n \log n\)f1=n log n과 \(f_{2}=n^{2}\)f2=n²입니다. n으로 묶으면 둘 다 n을 하나 가지므로 남는 log n과 n을 비교하면 됩니다. \(\log n/n\to 0\)log n/n→0이므로 log n은 n보다 느리고, 따라서 \(n \log n=o(n^{2})\)n log n=o(n²)입니다.
두 번째 비교는 \(f_{2}=n^{2}\)f2=n²와 \(f_{4}=n^{\log n}\)f4=n^(log n)입니다. 밑이 n으로 같으므로 지수 2와 log n을 비교합니다. log n은 무한히 커지므로 충분히 큰 n에서 \(\log n>2\)log n>2입니다. 따라서 \(n^{2}<n^{\log n}\)n²<n^(log n)입니다.
세 번째 비교는 \(f_{4}=n^{\log n}\)f4=n^(log n)과 \(f_{3}=2^{n}\)f3=2ⁿ입니다. log를 밑 2로 쓰면 \(n=2^{\log_{2}n}\)n=2^(log₂n)이므로 \(f_{4}=(2^{\log_{2}n})^{\log_{2}n}=2^{(\log_{2}n)^{2}}\)f4=(2^(log₂n))^(log₂n)=2^((log₂n)²)입니다. \(f_{3}\)f3는 \(2^{n}\)2ⁿ입니다.
밑이 둘 다 2가 되었으므로 지수만 비교합니다. \((\log_{2}n)^{2}/n\to 0\)(log₂n)²/n→0이므로 \((\log_{2}n)^{2}\)(log₂n)²는 n보다 작게 성장합니다. 따라서 \(2^{(\log_{2}n)^{2}}<2^{n},\)2^((log₂n)²)<2ⁿ,즉 \(f_{4}<f_{3}\)f4<f3입니다.
세 비교를 연결하면 \(n \log n<n^{2}<n^{\log n}<2^{n}\)n log n<n²<n^(log n)<2ⁿ이고, 함수 기호로는 \(f_{1}<f_{2}<f_{4}<f_{3}\)f1<f2<f4<f3입니다. 따라서 정확히 일치하는 B가 정답입니다.
이 풀이의 중심은 \(n^{\log n}\)n^(log n)을 '이상한 함수'로 방치하지 않고 두 방향에서 끼워 넣는 것입니다. 아래쪽에서는 지수 log n이 모든 고정 상수보다 커진다는 사실을 사용하고, 위쪽에서는 밑 2로 변환해 지수 \(\log^{2}n\)log²n이 n보다 작다는 사실을 사용합니다.
3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기
-
A거짓
\(f_{1}<f_{2}\)
f1<f2까지는 맞지만 \(f_{3}<f_{4}\)f3<f4가 틀렸습니다. \(f_{3}=2^{n}\)f3=2ⁿ이고 \(f_{4}=2^{\log^{2}n}\)f4=2^(log²n)이므로 충분히 큰 n에서는 \(f_{4}<f_{3}\)f4<f3입니다. 선택지는 일부가 맞아도 전체 순서 하나가 틀리면 오답입니다.빠른 확인법: \(n=32, \log_{2}n=5\)
n=32, log₂n=5를 넣으면 \(f_{4}=2^{25}, f_{3}=2^{32}\)f4=2²⁵, f3=2³²라서 A의 마지막 순서가 깨집니다. -
B참 — 정답 후보
\(f_{1}<f_{2}\)
f1<f2는 \(\log n<n, f_{2}<f_{4}\)log n<n, f2<f4는 \(2<\log n \text{eventually}, f_{4}<f_{3}\)2<log n eventually, f4<f3는 \(\log^{2}n<n \text{eventually}\)log²n<n eventually로 각각 증명됩니다. 세 인접 비교가 모두 맞는 유일한 선택지입니다.빠른 확인법: 계급표 \(n \log n < \text{fixed} \text{polynomial} < \text{quasipolynomial} < \text{exponential}\)
n log n < fixed polynomial < quasipolynomial < exponential과 정확히 일치합니다. -
C거짓
\(f_{4}<f_{2}\)
f4<f2라고 둔 부분이 반대입니다. \(f_{4}\)f4의 지수 log n은 고정된 2를 결국 넘어가므로 \(f_{4}\)f4가 \(f_{2}\)f2보다 큽니다.빠른 확인법: \(\log_{2}\)
log₂기준 \(n=8\)n=8이면 \(f_{4}=8^{3}=512\)f4=8³=512이고 \(f_{2}=64\)f2=64입니다. -
D거짓
\(f_{4}\)
f4를 가장 작게 둔 것부터 틀렸고 \(f_{2}<f_{1}\)f2<f1도 반대입니다. \(f_{4}\)f4는 모든 고정 차수 다항식보다 빠르며 n log n은 \(n^{2}\)n²보다 느립니다.빠른 확인법: 정확한 앞부분은 \(f_{1}<f_{2}<f_{4}\)
f1<f2<f4입니다.
4. 초보자가 가장 자주 틀리는 이유
- log n이 천천히 커진다는 이유로 상수라고 취급한다.
- \(n^{\log n}\)
n^(log n)을 겉모양만 보고 \(n^{k}\)nᵏ형태의 고정 차수 다항식으로 분류한다. - 지수함수라는 단어만 보고 \(n^{\log n}\)
n^(log n)이 \(2^{n}\)2ⁿ보다 빠르다고 생각한다. - \(n=2\)
n=2나 \(n=8\)n=8같은 작은 값 하나만 대입해 최종 점근 순서를 확정한다. - 선택지에서 앞의 두 항만 확인하고 뒤의 순서 교환을 놓친다.
- 로그 밑을 바꾸면 Θ-class가 달라진다고 생각한다.
- '<‘를 모든 n에서의 수치 부등식으로 읽는다. 이 문항에서는 충분히 큰 n에서의 성장률 비교입니다.
5. 시험 답안 템플릿
고정된 로그 밑을 가정한다. \(\log n=o(n)\)log n=o(n)이므로 \(n \log n=o(n^{2}).\)n log n=o(n²).또한 \(\log n>2 \text{eventually}\)log n>2 eventually이므로 \(n^{2}=o(n^{\log n}).\)n²=o(n^(log n)).마지막으로 \(n^{\log_{2}n}=2^{(\log_{2}n)^{2}}\)n^(log₂n)=2^((log₂n)²)이고 \((\log n)^{2}=o(n)\)(log n)²=o(n)이므로 \(n^{\log n}=o(2^{n}).\)n^(log n)=o(2ⁿ).따라서 \(f_{1}<f_{2}<f_{4}<f_{3}\)f1<f2<f4<f3이고 정답은 B이다.
6. 스스로 이해했는지 확인
n log n이 \(n^{2}\)n²보다 느리다는 것을 비율로 보이면?
정답: \((n \log n)/n^{2}=\log n/n\to 0\)(n log n)/n²=log n/n→0이므로 \(n \log n=o(n^{2})\)n log n=o(n²)입니다.
왜 \(n^{\log n}\)n^(log n)은 \(n^{100}\)n¹⁰⁰도 언젠가 추월하는가?
정답: log n은 무한히 증가해 결국 100보다 커지므로 같은 밑 n에서 \(n^{\log n}>n^{100}\)n^(log n)>n¹⁰⁰이 됩니다.
\(n^{\log_{2}n}\)n^(log₂n)을 밑 2로 바꾸면?
정답: \(n=2^{\log_{2}n}\)n=2^(log₂n)이므로 \(n^{\log_{2}n}=2^{(\log_{2}n)^{2}}\)n^(log₂n)=2^((log₂n)²)입니다.
\((\log n)^{2}\)(log n)²와 n 중 어느 쪽이 빠른가?
정답: n이 더 빠릅니다. \((\log n)^{2}=o(n)\)(log n)²=o(n)입니다.
log 밑이 10이면 결론이 바뀌는가?
정답: 바뀌지 않습니다. 고정 로그 밑의 변화는 상수배 차이만 만들며 성장급의 순서는 같습니다.
최종 순서를 함수 번호로 말하면?
정답: \(f_{1}<f_{2}<f_{4}<f_{3}\)f1<f2<f4<f3입니다.
근거 자료
AuD Gedächtnisprotokoll SoSe 2025.md· Multiple Choice I.1
복기된 문제 문언과 선택지Vorlesung\02Sorting_updated.pdf· pp. 31-48; data/aud_chunks.jsonl lines 198-203
점근 표기, 충분히 큰 n, O/Ω/Θ와 성장률 비교Übung\AuD26_Sheet02-Sol.pdf· pp. 1-4; data/aud_chunks.jsonl lines 13-14
Landau 표기와 polynomial/exponential 성장 비교 공식 해설