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

이진 탐색은 입력에 대해 무엇을 요구합니까?

1. A배열 길이가 2의 거듭제곱이어야 한다
2. B배열의 원소가 1000개를 넘지 않아야 한다
3. C배열에 양수만 있어야 한다
4. D배열이 정렬되어 있어야 한다

증가율의 상한(upper bound)을 나타내는 표기법은 무엇입니까?

1. ABig Omega
2. BBig Theta
3. CBig O
4. DLittle omega

log₂ 1024는 얼마입니까?

1. A512
2. B32
3. C12
4. D10

길이가 m과 n인 문자열의 최장 공통 부분 수열에 대한 표준 동적 계획법 알고리즘의 시간 복잡도는 무엇입니까?

1. AO(2^m+n)
2. BO(mn)
3. CO(mn log n)
4. DO(m + n)

안정(stable) 정렬 알고리즘은 무엇입니까?

1. A선택 정렬(일반적인 버전)
2. B병합 정렬
3. C퀵 정렬(일반적인 제자리 버전)
4. D힙 정렬

정렬된 배열에서 양 끝에서 포인터를 하나씩 안쪽으로 움직이며 합이 목표값인 두 원소를 찾습니다. 시간 복잡도는 무엇입니까?

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

어떤 입력에 대해서도 퀵 정렬의 기대(expected) 실행 시간을 O(n log n)으로 만드는 기법은 무엇입니까?

1. A피벗을 균등하게 무작위로 선택하기
2. B항상 첫 번째 원소를 선택하기
3. C왼쪽에만 재귀를 사용하기
4. D퀵 정렬을 실행하기 전에 입력을 정렬하기

log(n!)에 대한 올바른 한계는 무엇입니까?

1. AΘ(log n)
2. BΘ(n log n)
3. CΘ(n²)
4. DΘ(n)