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

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

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

이미 정렬된 배열에서 삽입 정렬의 최선의 경우 시간 복잡도는 무엇입니까?

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

선택 정렬(selection sort)은 어떻게 동작합니까?

1. A정렬되지 않은 부분의 최솟값을 반복해서 찾아 앞으로 교환한다
2. B순서가 잘못된 이웃 원소들을 반복해서 교환한다
3. C각 원소를 이동시키며 커지는 정렬된 부분에 삽입한다
4. D배열을 절반으로 나눈 뒤 병합한다

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

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

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

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

퀵 정렬의 최악의 경우 시간 복잡도는 무엇입니까?

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

헬드-카프 동적 계획법 알고리즘은 외판원 문제를 정확히 풉니다. 도시가 n개일 때 실행 시간은 얼마입니까?

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

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

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