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

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

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

이진 탐색은 입력에 대해 무엇을 요구합니까?

1. A배열에 양수만 있어야 한다
2. B배열 길이가 2의 거듭제곱이어야 한다
3. C배열의 원소가 1000개를 넘지 않아야 한다
4. D배열이 정렬되어 있어야 한다

n이 커질 때 다음 중 가장 느리게 증가하는 것은 무엇입니까?

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

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

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

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

1. A모든 경우에 Bellman–Ford가 필요함
2. BKruskal 알고리즘
3. C깊이 우선 탐색(DFS)
4. DDijkstra 알고리즘

가중치가 없는 그래프에서 너비 우선 탐색(BFS)은 무엇을 찾습니까?

1. A최소 신장 트리
2. B모든 그래프에서의 위상 순서
3. C음의 간선 가중치를 포함한 그래프에서의 최단 경로
4. D시작 노드로부터 간선 수 기준의 최단 경로

삽입 정렬은 정렬된 입력에서 O(n)에 실행됩니다. 이것은 비교 정렬의 Ω(n log n) 하한과 모순됩니까?

1. A예, 단 길이가 100보다 짧은 배열에서만
2. B아니요, 하한은 모든 입력이 아니라 모든 입력에 걸친 최악의 경우에 적용된다
3. C예, 따라서 하한이 틀렸다
4. D아니요, 삽입 정렬은 비교 정렬이 아니기 때문에

마스터 정리를 사용하면 T(n) = 8T(n/2) + O(n²)의 해는 무엇입니까?

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