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

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

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

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

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

순서가 잘못된 인접 원소를 반복적으로 교환하는 정렬 알고리즘은 무엇입니까?

1. A힙 정렬(Heap sort)
2. B퀵 정렬(Quicksort)
3. C병합 정렬(Merge sort)
4. D버블 정렬(Bubble sort)

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

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

분할 상환 분석(amortised analysis)은 무엇을 측정합니까?

1. A최악의 연산 순서에 걸친 연산당 평균 비용
2. B최선의 입력에서 알고리즘의 비용
3. C연산열 전체에서 가장 비싼 단일 연산 하나의 비용
4. D무작위 입력에 대한 기대 비용

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

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

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

1. A다항이 아닌 문제
2. B다항 시간에 풀 수 없는 문제
3. C인증서가 주어지면 "예" 답을 다항 시간에 검증할 수 있는 결정 문제
4. D어떤 알고리즘으로도 풀 수 없는 문제

정렬된 배열에서 비교 기반 탐색은 왜 최악의 경우 Ω(log n)번의 비교가 필요합니까?

1. A가능한 결과가 n개인 결정 트리는 깊이가 최소 log₂ n이어야 하기 때문에
2. B이진 탐색이 유일하게 가능한 알고리즘이며 log₂ n번의 비교가 필요하기 때문에
3. C모든 원소를 최소 한 번은 비교해야 하기 때문에
4. D비교 하나하나가 로그 시간이 걸리기 때문에