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

각각 n번 실행되는 두 개의 중첩 루프를 가진 알고리즘은 일반적으로 어떤 복잡도를 가집니까?

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

n이 클 때 가장 빠르게 증가하는 복잡도 클래스는 무엇입니까?

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

표준 배열 기반 병합 정렬은 추가 메모리를 얼마나 사용합니까?

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

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

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

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

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

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

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

해시 테이블의 평균 조회 시간은 O(1)인데 최악의 경우는 O(n)인 이유는 무엇입니까?

1. A많은 키가 같은 버킷에서 충돌(collision)할 수 있기 때문이다
2. B해시 함수가 느리기 때문이다
3. C배열 접근이 O(n)이기 때문이다
4. D키를 먼저 정렬해야 하기 때문이다

어떤 문제가 NP-완전(NP-complete)이려면 어떤 조건을 만족해야 합니까?

1. A푸는 것이 불가능하다
2. BNP 밖에 있으면서 정지 문제처럼 모든 NP 문제보다 어렵다
3. CNP에 속하고 모든 NP 문제가 다항 시간에 그 문제로 환원된다
4. D다항 시간에 풀 수 있다