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

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

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

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

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

알고리즘의 실행 시간이 O(n)입니다. 이 증가를 무엇이라고 합니까?

1. A로그
2. B선형
3. C상수
4. D이차

도달 가능한 기저 사례가 없는 재귀 함수에 대한 진술 중 옳은 것은 무엇입니까?

1. A자동으로 0을 반환한다
2. B컴파일러가 항상 안전하게 끝나는 루프로 바꾼다
3. C호출 스택이 넘칠 때까지 계속 자신을 호출한다
4. DO(1) 시간에 실행된다

많은 라이브러리 정렬 루틴이 아주 작은 부분 배열에서 삽입 정렬로 전환하는 이유는 무엇입니까?

1. A재귀 알고리즘은 원소가 10개 미만인 배열을 처리하지 못하기 때문에
2. B큰 입력에서 삽입 정렬이 다른 어떤 정렬 알고리즘보다 메모리를 적게 쓰기 때문에
3. C삽입 정렬은 오버헤드가 적고 작거나 거의 정렬된 입력에서 빠르기 때문에
4. D삽입 정렬은 최악의 경우 O(n log n)이기 때문에

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

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

슈트라센 알고리즘은 절반 크기 블록의 재귀 곱셈을 8번 대신 7번 사용하여 행렬을 곱합니다. 실행 시간은 얼마입니까?

1. AΘ(n²)
2. BΘ(n^{log₂ 7}), 약 n^2.81
3. CΘ(n² log n)
4. DΘ(n³)

어떤 문제가 NP-완전(NP-complete)이려면 어떤 조건을 만족해야 합니까?

1. A푸는 것이 불가능하다
2. B다항 시간에 풀 수 있다
3. CNP 밖에 있으면서 정지 문제처럼 모든 NP 문제보다 어렵다
4. DNP에 속하고 모든 NP 문제가 다항 시간에 그 문제로 환원된다