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

루프가 i = 1에서 시작하여 i > n이 될 때까지 매 반복마다 i를 두 배로 합니다. 몇 번 반복합니까?

1. A약 n
2. B약 n / 2
3. C약 log₂ n
4. D약 n²

재귀란 무엇입니까?

1. A자료 구조의 한 종류
2. B절대 끝나지 않는 루프
3. C정렬 방법의 하나
4. D더 작은 입력에 대해 자기 자신을 호출하는 함수

다음 실행 시간 중 다항 시간은 무엇입니까?

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

원소 n개의 배열에 대한 병합 정렬의 재귀에는 몇 개의 단계가 있습니까?

1. A약 n / 2
2. B약 n
3. C약 √n
4. D약 log₂ n

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

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

단순한 재귀 팩토리얼 함수 fact(n) = n × fact(n − 1)은 스택 공간을 얼마나 사용합니까?

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

2²ⁿ은 O(2ⁿ)에 속합니까?

1. A아니요, 2²ⁿ = 4ⁿ이고 4ⁿ / 2ⁿ = 2ⁿ은 한없이 커지기 때문에
2. B예, 지수의 상수 계수는 Big O에서 항상 무시되기 때문에
3. C아니요, 2²ⁿ이 2ⁿ보다 느리게 증가하기 때문에
4. D예, 둘 다 지수이기 때문에

마지막 두 값만 유지하는 루프로 n번째 피보나치 수를 계산할 때 시간과 공간 비용은 얼마입니까?

1. AO(log n) 시간과 O(n) 공간
2. BO(n) 시간과 O(n) 공간
3. CO(n) 시간과 O(1) 공간
4. DO(2ⁿ) 시간과 O(1) 공간