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

0부터 k까지 범위의 정수 n개에 대한 계수 정렬(counting sort)의 실행 시간은 얼마입니까?

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

3n² + 5n + 2의 Big O는 무엇입니까?

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

각각 n번 실행되는 두 개의 중첩 루프를 가진 알고리즘은 일반적으로 어떤 복잡도를 가집니까?

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

원소 n개의 배열에 대한 병합 정렬의 재귀에는 몇 개의 단계가 있습니까?

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

O(log n)처럼 Big O에서 로그의 밑을 보통 생략하는 이유는 무엇입니까?

1. A밑이 다른 로그는 상수배만큼만 다르기 때문에
2. B밑은 n이 작을 때만 중요하기 때문에
3. C로그는 항상 정수로 반올림되기 때문에
4. D컴퓨터 과학의 모든 로그는 밑이 10이므로 생략해도 알 수 있기 때문에

O(n²) 알고리즘이 O(n³)이기도 하다고 말하는 것은 옳습니까?

1. A예, 단 n이 100보다 작을 때만
2. B아니요, Big O는 함수의 정확한 증가율을 항상 나타내야 하기 때문에
3. C아니요, 큰 n에서 n³이 n²보다 작기 때문에
4. D예, Big O는 상한이고 n²은 n³보다 빠르게 증가하지 않기 때문에

단일 연결 리스트에서 이진 탐색이 O(log n) 시간을 주지 못하는 이유는 무엇입니까?

1. A이진 탐색에는 최소 두 배의 메모리가 필요하기 때문에
2. B연결 리스트 노드의 비교가 더 느리기 때문에
3. C연결 리스트는 정렬할 수 없기 때문에
4. D직접 인덱스 접근이 없으므로 가운데 원소에 도달하는 데 O(n) 단계가 걸리기 때문에

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

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