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

n개의 수로 된 정렬되지 않은 배열에서 가장 큰 값을 찾는 시간 복잡도는 무엇입니까?

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

문제가 보통 다루기 쉽다(tractable)고 불리는 것은 언제입니까?

1. A상수 시간에 풀 수 있을 때
2. B모든 가능성을 시도해야만 풀 수 있을 때
3. C해가 없을 때
4. D다항 시간에 풀 수 있을 때

n이 클 때 가장 빠르게 증가하는 복잡도 클래스는 무엇입니까?

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

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

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

탐욕 알고리즘(greedy algorithm)은 무엇을 합니까?

1. A각 단계에서 지역적으로 가장 좋은 선택을 합니다
2. B항상 최적해를 제공합니다
3. C재귀만 사용합니다
4. D가능한 모든 해를 시도합니다

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

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

little-o 표기법에 대한 진술 중 옳은 것은 무엇입니까?

1. A2n은 느리게 증가하므로 2n = o(n)
2. Bn² = o(n)
3. C모든 함수는 자기 자신의 little-o이므로 n = o(n)
4. Dn = o(n²)이지만 n은 o(n)이 아니다

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

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