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

log₂ 1024는 얼마입니까?

1. A32
2. B512
3. C10
4. D12

알고리즘이란 무엇입니까?

1. A그래픽 인터페이스가 있는 모든 컴퓨터 프로그램
2. B수학 공식을 쓰기 위해 설계된 프로그래밍 언어
3. C문제를 해결하는 잘 정의된 단계들의 유한한 순서
4. D수를 저장하는 자료 구조

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

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

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

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

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

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

분할 상환 분석(amortised analysis)은 무엇을 측정합니까?

1. A최악의 연산 순서에 걸친 연산당 평균 비용
2. B무작위 입력에 대한 기대 비용
3. C최선의 입력에서 알고리즘의 비용
4. D연산열 전체에서 가장 비싼 단일 연산 하나의 비용

외판원 문제는 어떻게 분류됩니까?

1. A결정 버전은 NP-complete이고 최적화 버전은 NP-hard이다
2. B결정 버전은 P에 속하지만 최적화 버전은 NP-complete이다
3. C다익스트라 알고리즘이 모든 도시를 한 번씩 방문하여 풀기 때문에 P에 속한다
4. D결정 불가능하다

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

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