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

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

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

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

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

이미 정렬된 배열에서 삽입 정렬의 최선의 경우 시간 복잡도는 무엇입니까?

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

많은 라이브러리 정렬 루틴이 아주 작은 부분 배열에서 삽입 정렬로 전환하는 이유는 무엇입니까?

1. A삽입 정렬은 오버헤드가 적고 작거나 거의 정렬된 입력에서 빠르기 때문에
2. B큰 입력에서 삽입 정렬이 다른 어떤 정렬 알고리즘보다 메모리를 적게 쓰기 때문에
3. C삽입 정렬은 최악의 경우 O(n log n)이기 때문에
4. D재귀 알고리즘은 원소가 10개 미만인 배열을 처리하지 못하기 때문에

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

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

for i = 1 to n: for j = 1 to i: O(1) 작업 수행 — 이 코드의 시간 복잡도는 무엇입니까?

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

쿡-레빈 정리는 무엇을 확립했습니까?

1. A정지 문제는 결정 불가능하다
2. BP는 NP와 같지 않다
3. C불리언 충족 가능성 문제(SAT)는 NP-complete이다
4. D모든 NP 문제는 지수 시간에 풀 수 있다

정렬된 배열에서 비교 기반 탐색은 왜 최악의 경우 Ω(log n)번의 비교가 필요합니까?

1. A이진 탐색이 유일하게 가능한 알고리즘이며 log₂ n번의 비교가 필요하기 때문에
2. B가능한 결과가 n개인 결정 트리는 깊이가 최소 log₂ n이어야 하기 때문에
3. C비교 하나하나가 로그 시간이 걸리기 때문에
4. D모든 원소를 최소 한 번은 비교해야 하기 때문에