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

O(n²) 알고리즘이 n = 1000에서 1초 걸립니다. n = 2000에서는 대략 얼마나 걸립니까?

1. A1초
2. B4초
3. C8초
4. D2초

메모이제이션(memoisation)이란 무엇입니까?

1. A코드의 각 줄 옆에 주석을 쓰는 것
2. B재귀를 동등한 루프로 자동 변환하여 호출 스택이 필요 없게 만드는 것
3. C함수 호출 결과를 저장하여 반복 호출에 메모리에서 답하는 것
4. D함수가 반환된 뒤 메모리를 해제하는 것

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

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

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

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

상향식 표로 n번째 피보나치 수를 계산하는 시간 복잡도는 무엇입니까?

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

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

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

쿡-레빈 정리는 무엇을 확립했습니까?

1. A모든 NP 문제는 지수 시간에 풀 수 있다
2. B불리언 충족 가능성 문제(SAT)는 NP-complete이다
3. CP는 NP와 같지 않다
4. D정지 문제는 결정 불가능하다

한 번 증가할 때 많은 비트가 뒤집힐 수 있다는 점을 고려할 때, 이진 카운터 증가의 분할 상환 비용은 얼마입니까?

1. A증가당 O(log n)
2. B증가당 O(n log n)
3. C증가당 O(1)
4. D증가당 O(n)