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

O(n²) 알고리즘이 n = 1000에서 1초 걸립니다. n = 2000에서는 대략 얼마나 걸립니까?

1. A1초
2. B4초
3. C8초
4. D2초

무차별 대입(brute-force) 알고리즘이란 무엇입니까?

1. A가능한 모든 후보 해를 시도하는 알고리즘
2. B무작위로 답을 추측하는 알고리즘
3. C항상 재귀를 사용하는 알고리즘
4. D여러 프로세서에서 실행되는 알고리즘

증가율의 상한(upper bound)을 나타내는 표기법은 무엇입니까?

1. ABig Theta
2. BLittle omega
3. CBig Omega
4. DBig O

플로이드-워셜 알고리즘은 무엇을 얼마나 빠르게 계산합니까?

1. A한 출발 정점에서 다른 모든 정점까지의 최단 경로를 O(V + E)에
2. B모든 정점 쌍 사이의 최단 경로를 O(V³)에
3. C최소 신장 트리를 O(E log V)에
4. D위상 정렬 순서를 O(V²)에

퀵 정렬이 항상 첫 원소를 피벗으로 사용합니다. 어떤 입력에서 최악의 경우 동작을 보입니까?

1. A무작위 순서의 배열
2. B길이가 2인 배열
3. C이미 정렬된 배열
4. D원소가 모두 다른 배열

프림 알고리즘은 최소 신장 트리를 어떻게 만듭니까?

1. A너비 우선 탐색을 실행하고 BFS 트리를 유지한다
2. B사이클이 없어질 때까지 가장 비싼 간선을 제거한다
3. C시작 정점에서 트리 하나를 키우며 트리를 떠나는 가장 싼 간선을 추가한다
4. D간선을 가중치순으로 모두 정렬하여 숲에서 사이클을 만들지 않는 간선을 하나씩 추가한다

마지막 두 값만 유지하는 루프로 n번째 피보나치 수를 계산할 때 시간과 공간 비용은 얼마입니까?

1. AO(n) 시간과 O(1) 공간
2. BO(2ⁿ) 시간과 O(1) 공간
3. CO(log n) 시간과 O(n) 공간
4. DO(n) 시간과 O(n) 공간

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

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