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

피벗을 골라 배열을 더 작은 원소와 더 큰 원소로 분할하는 정렬 알고리즘은 무엇입니까?

1. A퀵 정렬
2. B삽입 정렬
3. C버블 정렬
4. D병합 정렬

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

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

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

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

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

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

안정(stable) 정렬 알고리즘은 무엇입니까?

1. A퀵 정렬(일반적인 제자리 버전)
2. B병합 정렬
3. C선택 정렬(일반적인 버전)
4. D힙 정렬

밑이 k이고 자릿수가 d인 정수 n개에 대한 LSD 기수 정렬의 실행 시간은 얼마입니까?

1. AO(dn log k)
2. BO(n²)
3. CO(d(n + k))
4. DO(n log n)

정점 V개, 간선 E개인 그래프에서 이진 힙을 사용한 다익스트라 알고리즘의 실행 시간은 얼마입니까?

1. AO(V × E)
2. BO(V³)
3. CO((V + E) log V)
4. DO(V + E)

위상 정렬은 어떤 그래프에서만 가능합니까?

1. A무방향 그래프
2. B음의 가중치를 가진 그래프
3. C방향성 비순환 그래프(DAG)
4. D완전 그래프