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

3n² + 5n + 2의 Big O는 무엇입니까?

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

정렬된 배열에서 이진 탐색(binary search)의 시간 복잡도는 무엇입니까?

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

O(2ⁿ) 증가를 무엇이라고 합니까?

1. A다항
2. B지수
3. C로그
4. D선형

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

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

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

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

함수가 n번 반복하는 루프 하나를 실행한 뒤, 따로 n번 반복하는 또 다른 루프를 실행합니다. 시간 복잡도는 무엇입니까?

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

일부 간선 가중치가 음수일 때 다익스트라 알고리즘이 틀린 결과를 줄 수 있는 이유는 무엇입니까?

1. A우선순위 큐에 음수를 저장할 수 없기 때문에
2. B정점은 추출될 때 확정되지만, 나중의 음수 간선이 여전히 더 짧은 경로를 줄 수 있기 때문에
3. C무방향 그래프에서만 동작하기 때문에
4. D음수 간선마다 무한 루프에 빠지기 때문에

큰 n에서 n!과 2ⁿ은 어떻게 비교됩니까?

1. A2ⁿ이 n!보다 빠르게 증가한다
2. B같은 비율로 증가한다
3. Cn!은 O(n²)이다
4. Dn!이 2ⁿ보다 빠르게 증가한다