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

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

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

분할 정복 알고리즘의 세 단계는 무엇입니까?

1. A추측, 확인, 반복
2. B읽기, 계산, 쓰기
3. C정렬, 탐색, 반환
4. D분할, 정복, 결합

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

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

활동 선택 문제에서 겹치지 않는 활동의 수를 항상 최대로 만드는 탐욕적 규칙은 무엇입니까?

1. A가장 일찍 시작하는 활동을 고른다
2. B가장 일찍 끝나는 활동을 고르고, 호환되는 활동들로 반복한다
3. C겹침이 가장 적은 활동을 먼저 고른 뒤, 호환되는 활동들로 반복한다
4. D가장 짧은 활동을 먼저 고른다

간선 가중치가 음이 아닌 그래프에서 하나의 출발점으로부터 최단 경로를 찾는 알고리즘은 무엇입니까?

1. ADijkstra 알고리즘
2. B모든 경우에 Bellman–Ford가 필요함
3. CKruskal 알고리즘
4. D깊이 우선 탐색(DFS)

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

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

클래스 NP의 올바른 정의는 무엇입니까?

1. A인증서가 주어지면 "예" 답을 다항 시간에 검증할 수 있는 결정 문제
2. B다항이 아닌 문제
3. C다항 시간에 풀 수 없는 문제
4. D어떤 알고리즘으로도 풀 수 없는 문제

단일 연결 리스트에서 이진 탐색이 O(log n) 시간을 주지 못하는 이유는 무엇입니까?

1. A이진 탐색에는 최소 두 배의 메모리가 필요하기 때문에
2. B직접 인덱스 접근이 없으므로 가운데 원소에 도달하는 데 O(n) 단계가 걸리기 때문에
3. C연결 리스트 노드의 비교가 더 느리기 때문에
4. D연결 리스트는 정렬할 수 없기 때문에