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

알고리즘의 최악의 경우 실행 시간은 무엇을 나타냅니까?

1. A크기 n인 무작위 입력에서 걸리는 기대 시간
2. B가장 작은 입력에서 걸리는 시간
3. C크기 n인 모든 입력 중에서 걸리는 최대 시간
4. D느린 컴퓨터에서 걸리는 시간

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

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

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

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

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

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

표준 삼중 루프로 두 n × n 행렬을 곱하는 시간 복잡도는 무엇입니까?

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

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

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

어떤 입력에 대해서도 퀵 정렬의 기대(expected) 실행 시간을 O(n log n)으로 만드는 기법은 무엇입니까?

1. A퀵 정렬을 실행하기 전에 입력을 정렬하기
2. B왼쪽에만 재귀를 사용하기
3. C항상 첫 번째 원소를 선택하기
4. D피벗을 균등하게 무작위로 선택하기

정렬되지 않은 배열에서 k번째로 작은 원소를 선택하는 것에 대한 진술 중 옳은 것은 무엇입니까?

1. A선택은 정렬이 필요하므로 항상 Ω(n log n)이 필요하다
2. B퀵셀렉트는 기대 O(n)에 실행되고, 중앙값의 중앙값은 최악의 경우 O(n)을 보장한다
3. C퀵셀렉트는 피벗의 한쪽에만 재귀하므로 최악의 경우에도 O(log n)에 실행된다
4. D선택은 O(n²)에만 가능하다