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

알고리즘이란 무엇입니까?

1. A수학 공식을 쓰기 위해 설계된 프로그래밍 언어
2. B그래픽 인터페이스가 있는 모든 컴퓨터 프로그램
3. C수를 저장하는 자료 구조
4. D문제를 해결하는 잘 정의된 단계들의 유한한 순서

이진 탐색은 입력에 대해 무엇을 요구합니까?

1. A배열에 양수만 있어야 한다
2. B배열 길이가 2의 거듭제곱이어야 한다
3. C배열이 정렬되어 있어야 한다
4. D배열의 원소가 1000개를 넘지 않아야 한다

정렬된 배열에서 이진 탐색(binary search)의 시간 복잡도는 무엇입니까?

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

가득 차면 용량을 두 배로 늘리는 동적 배열에 원소를 추가하는 연산의 분할 상환(amortised) 시간 복잡도는 무엇입니까?

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

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

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

정렬된 배열에서 양 끝에서 포인터를 하나씩 안쪽으로 움직이며 합이 목표값인 두 원소를 찾습니다. 시간 복잡도는 무엇입니까?

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

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

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

마스터 정리를 사용하면 T(n) = 8T(n/2) + O(n²)의 해는 무엇입니까?

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