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

루프가 i = 1에서 시작하여 i > n이 될 때까지 매 반복마다 i를 두 배로 합니다. 몇 번 반복합니까?

1. A약 n / 2
2. B약 n²
3. C약 n
4. D약 log₂ n

순서가 잘못된 인접 원소를 반복적으로 교환하는 정렬 알고리즘은 무엇입니까?

1. A퀵 정렬(Quicksort)
2. B병합 정렬(Merge sort)
3. C힙 정렬(Heap sort)
4. D버블 정렬(Bubble sort)

f(n) = Θ(g(n))은 무엇을 의미합니까?

1. Af는 g보다 엄격히 빠르게 증가한다
2. Bf는 g보다 엄격히 느리게 증가한다
3. C모든 n에 대해 f가 항상 g보다 작으므로, g가 위에서는 한정하지만 아래에서는 한정하지 않는다
4. Df는 g와 같은 비율로 증가하며, 위아래로 g의 상수배에 의해 한정된다

동적 계획법이 병합 정렬에 실질적인 속도 향상을 주지 못하는 이유는 무엇입니까?

1. A병합 정렬은 이미 O(n)이기 때문에
2. B병합 정렬에는 재귀 구조가 없기 때문에
3. C동적 계획법은 배열이 아니라 그래프 문제에서만 동작하기 때문에
4. D부분 문제가 겹치지 않아 재사용할 것이 없기 때문에

최악의 경우 비교 기반 정렬의 하한은 무엇입니까?

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

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

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

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

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

다음 충족 가능성 문제 중 다항 시간에 풀 수 있다고 알려진 것은 무엇입니까?

1. A논리곱 표준형 식에 대한 일반 SAT
2. B회로 충족 가능성
3. C각 절에 리터럴이 최대 두 개인 2-SAT
4. D각 절에 리터럴이 정확히 세 개인 3-SAT