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

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

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

어떤 연산이 O(1) 시간에 실행된다는 것은 무엇을 의미합니까?

1. A한 번만 실행할 수 있다
2. B실행 시간이 입력 크기에 따라 증가하지 않는다
3. C항상 정확히 1초가 걸린다
4. D실행 시간 1초마다 정확히 원소 하나를 처리한다

다음 실행 시간 중 다항 시간은 무엇입니까?

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

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

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

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

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

for i = 1 to n: (j = 1; while j < n: j = j × 2) — 이 코드의 시간 복잡도는 무엇입니까?

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

클래스 P의 올바른 정의는 무엇입니까?

1. A결정적 알고리즘으로 다항 시간에 풀 수 있는 결정 문제
2. B병렬로 풀 수 있는 문제
3. C모든 컴퓨터에서 지수 시간이 필요한 문제
4. D해를 다항 시간에 검증할 수는 있지만 찾는 것은 절대 불가능한 문제

한 번 증가할 때 많은 비트가 뒤집힐 수 있다는 점을 고려할 때, 이진 카운터 증가의 분할 상환 비용은 얼마입니까?

1. A증가당 O(n log n)
2. B증가당 O(log n)
3. C증가당 O(1)
4. D증가당 O(n)