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

문제가 보통 다루기 쉽다(tractable)고 불리는 것은 언제입니까?

1. A해가 없을 때
2. B모든 가능성을 시도해야만 풀 수 있을 때
3. C상수 시간에 풀 수 있을 때
4. D다항 시간에 풀 수 있을 때

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

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

O(2ⁿ) 증가를 무엇이라고 합니까?

1. A다항
2. B지수
3. C선형
4. D로그

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

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

문제가 최적 부분 구조를 가진다는 것은 무엇을 의미합니까?

1. A문제를 상수 시간에 풀 수 있다
2. B모든 부분 문제의 크기가 같다
3. C최적해를 부분 문제들의 최적해로부터 만들 수 있다
4. D문제의 최적해가 정확히 하나이며 모든 부분 문제가 그것을 공유한다

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

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

동적 프로그래밍으로 푸는 0/1 배낭 문제는 O(nW) 시간이 걸립니다. 이것을 의사 다항 시간(pseudo-polynomial)이라고 부르는 이유는 무엇입니까?

1. A알고리즘이 무작위화되어 있어 입력마다 실행 시간이 달라지기 때문이다
2. Bn이 항상 작기 때문이다
3. CW = 0일 때만 작동하기 때문이다
4. DW는 수이므로 실행 시간이 W를 쓰는 데 쓰이는 비트 수에 대해 지수적이다

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

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