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

알고리즘의 실행 시간이 O(n)입니다. 이 증가를 무엇이라고 합니까?

1. A상수
2. B로그
3. C선형
4. D이차

분할 정복 알고리즘의 세 단계는 무엇입니까?

1. A정렬, 탐색, 반환
2. B추측, 확인, 반복
3. C읽기, 계산, 쓰기
4. D분할, 정복, 결합

정렬된 배열에서 이진 탐색(binary search)의 시간 복잡도는 무엇입니까?

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

퀵 정렬의 최악의 경우 시간 복잡도는 무엇입니까?

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

동적 프로그래밍(dynamic programming)은 문제가 무엇을 가질 때 유용합니까?

1. A중복되는 부분 문제와 최적 부분 구조
2. B부분 문제가 전혀 없어 한 단계로 풀 수 있음
3. C루프가 하나뿐임
4. D무작위 입력만 있음

단순 재귀 피보나치(fib(n) = fib(n−1) + fib(n−2))의 시간 복잡도는 무엇입니까?

1. A상수 시간
2. B로그 시간
3. C지수 시간
4. D선형 시간

카라추바 곱셈은 T(n) = 3T(n/2) + O(n)을 만족합니다. 해는 무엇입니까?

1. AΘ(n³)
2. BΘ(n log n)
3. CΘ(n²)
4. DΘ(n^{log₂ 3}), 약 n^1.585

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

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