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

n개의 원소를 가진 정렬되지 않은 배열에서 선형 탐색(linear search)의 시간 복잡도(최악의 경우)는 무엇입니까?

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

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

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

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

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

for i = 1 to n: (j = 1; while j < n: j = j × 2) — 이 코드의 시간 복잡도는 무엇입니까?

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

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

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

원소가 1,000,000개인 정렬된 배열에서 이진 탐색은 최악의 경우 대략 몇 번 비교합니까?

1. A약 20
2. B약 100
3. C약 1,000
4. D약 500,000

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

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

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

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