정답이 있는 알고리즘과 복잡도 학습지

재귀 함수의 기저 사례(base case)란 무엇입니까?

1. A메모리를 가장 많이 쓰는 호출
2. B함수의 첫 줄
3. C입력이 가장 큰 경우로, 재귀 호출보다 먼저 처리된다
4. D또 다른 재귀 호출 없이 직접 답을 내는 경우

n이 클 때 가장 빠르게 증가하는 복잡도 클래스는 무엇입니까?

1. AO(n²)
2. BO(n³)
3. CO(2ⁿ)
4. DO(n log n)

n개의 원소를 가진 정렬되지 않은 배열에서 선형 탐색(linear search)의 시간 복잡도(최악의 경우)는 무엇입니까?

1. AO(log n)
2. BO(n)
3. CO(n²)
4. DO(1)

표준 삼중 루프로 두 n × n 행렬을 곱하는 시간 복잡도는 무엇입니까?

1. AO(n²)
2. BO(n³)
3. CO(n)
4. DO(n² log n)

원소 n개의 배열을 한 번 정렬한 뒤 이진 탐색으로 k개의 소속 질의에 답합니다. 전체 비용은 얼마입니까?

1. AO(nk)
2. BO(n log n + k log n)
3. CO(k n log n)
4. DO(n + k)

가득 차면 용량을 두 배로 늘리는 동적 배열에 원소를 추가하는 연산의 분할 상환(amortised) 시간 복잡도는 무엇입니까?

1. AO(log n)
2. BO(n)
3. CO(1)
4. DO(n²)

큰 n에서 n!과 2ⁿ은 어떻게 비교됩니까?

1. A같은 비율로 증가한다
2. Bn!은 O(n²)이다
3. C2ⁿ이 n!보다 빠르게 증가한다
4. Dn!이 2ⁿ보다 빠르게 증가한다

삽입 정렬은 정렬된 입력에서 O(n)에 실행됩니다. 이것은 비교 정렬의 Ω(n log n) 하한과 모순됩니까?

1. A예, 따라서 하한이 틀렸다
2. B아니요, 삽입 정렬은 비교 정렬이 아니기 때문에
3. C아니요, 하한은 모든 입력이 아니라 모든 입력에 걸친 최악의 경우에 적용된다
4. D예, 단 길이가 100보다 짧은 배열에서만