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

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

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

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

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

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

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

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

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

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

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

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

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

for i = 1 to n: for (j = i; j ≤ n; j = j + i) O(1) 작업 수행 — 이 코드의 시간 복잡도는 무엇입니까?

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

결정 문제 X가 NP-complete임을 증명하려면 어떤 두 가지를 보여야 합니까?

1. AX가 NP에 속하고, 알려진 NP-complete 문제가 다항 시간에 X로 환원된다
2. BX에 다항 알고리즘이 없고, X가 결정 가능하다
3. CX가 P에 속하고, X가 SAT로 환원된다
4. DX가 P에 속하는 문제로 환원되고, X가 NP에 속한다