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

삽입 정렬(insertion sort)의 최악의 경우 시간 복잡도는 무엇입니까?

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

배열에서 인덱스로 원소에 접근하는 데 걸리는 시간은 무엇입니까?

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

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

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

동전이 1, 3, 4이고 금액이 6일 때, 탐욕적인 "가장 큰 동전 먼저" 방법은 최적과 비교하여 동전을 몇 개 사용합니까?

1. A탐욕은 3개, 최적은 2개
2. B탐욕은 4개, 최적은 3개
3. C탐욕은 2개, 최적은 2개
4. D탐욕은 3개, 최적은 3개

함수가 n번 반복하는 루프 하나를 실행한 뒤, 따로 n번 반복하는 또 다른 루프를 실행합니다. 시간 복잡도는 무엇입니까?

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

단순 재귀 피보나치(fib(n) = fib(n−1) + fib(n−2))의 시간 복잡도는 무엇입니까?

1. A지수 시간
2. B로그 시간
3. C선형 시간
4. D상수 시간

큰 n에서 n!과 2ⁿ은 어떻게 비교됩니까?

1. An!은 O(n²)이다
2. B2ⁿ이 n!보다 빠르게 증가한다
3. Cn!이 2ⁿ보다 빠르게 증가한다
4. D같은 비율로 증가한다

점화식 T(n) = 2T(n/2) + n log n의 해는 무엇입니까?

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