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

삽입 정렬(insertion sort)의 최악의 경우 시간 복잡도는 무엇입니까?

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

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

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

log₂ 1024는 얼마입니까?

1. A512
2. B10
3. C12
4. D32

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

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

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

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

O(n²) 알고리즘이 O(n³)이기도 하다고 말하는 것은 옳습니까?

1. A아니요, Big O는 함수의 정확한 증가율을 항상 나타내야 하기 때문에
2. B예, Big O는 상한이고 n²은 n³보다 빠르게 증가하지 않기 때문에
3. C예, 단 n이 100보다 작을 때만
4. D아니요, 큰 n에서 n³이 n²보다 작기 때문에

최단 단순 경로는 다항 시간에 찾을 수 있습니다. 일반 그래프에서 두 정점 사이의 최장 단순 경로를 찾는 것에 대해 알려진 것은 무엇입니까?

1. A항상 O(V + E)에 풀 수 있다
2. B결정 불가능하다
3. C가중치를 음수로 바꾼 다익스트라 알고리즘으로 풀 수 있다
4. DNP-hard이다

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

1. AΘ(n log n)
2. BΘ(n log² n)
3. CΘ(n)
4. DΘ(n²)