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

n개의 수로 된 정렬되지 않은 배열에서 가장 큰 값을 찾는 시간 복잡도는 무엇입니까?

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

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

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

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

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

많은 라이브러리 정렬 루틴이 아주 작은 부분 배열에서 삽입 정렬로 전환하는 이유는 무엇입니까?

1. A삽입 정렬은 오버헤드가 적고 작거나 거의 정렬된 입력에서 빠르기 때문에
2. B재귀 알고리즘은 원소가 10개 미만인 배열을 처리하지 못하기 때문에
3. C큰 입력에서 삽입 정렬이 다른 어떤 정렬 알고리즘보다 메모리를 적게 쓰기 때문에
4. D삽입 정렬은 최악의 경우 O(n log n)이기 때문에

최악의 경우 비교 기반 정렬의 하한은 무엇입니까?

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

점화식 T(n) = T(n − 1) + O(n)의 해는 무엇입니까?

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

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

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

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

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