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

0부터 k까지 범위의 정수 n개에 대한 계수 정렬(counting sort)의 실행 시간은 얼마입니까?

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

3n² + 5n + 2의 Big O는 무엇입니까?

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

배열에서 인덱스로 원소에 접근하는 데 걸리는 시간은 무엇입니까?

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

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

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

상향식 표로 n번째 피보나치 수를 계산하는 시간 복잡도는 무엇입니까?

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

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

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

새 문제 X가 NP-hard임을 보이려면 무엇을 해야 합니까?

1. AX를 다항 시간에 검증할 수 있음을 보인다
2. B작은 입력에서 X에 다항 알고리즘이 없음을 보인다
3. C알려진 NP-hard 문제를 다항 시간에 X로 환원한다
4. DX를 다항 시간에 알려진 NP-hard 문제로 환원한다

헬드-카프 동적 계획법 알고리즘은 외판원 문제를 정확히 풉니다. 도시가 n개일 때 실행 시간은 얼마입니까?

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