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

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

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

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

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

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

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

표준 삼중 루프로 두 n × n 행렬을 곱하는 시간 복잡도는 무엇입니까?

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

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

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

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

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

누군가 NP-complete 문제 하나에 대한 다항 시간 알고리즘을 찾는다면 어떤 결과가 따릅니까?

1. ANP의 모든 문제를 다항 시간에 풀 수 있으므로 P = NP이다
2. B정지 문제가 결정 가능해진다
3. C모든 지수 시간 알고리즘이 즉시 선형 시간에 실행된다
4. D그 문제 하나만 P로 옮겨진다

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

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