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

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

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

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

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

재귀 함수의 기저 사례(base case)란 무엇입니까?

1. A메모리를 가장 많이 쓰는 호출
2. B또 다른 재귀 호출 없이 직접 답을 내는 경우
3. C함수의 첫 줄
4. D입력이 가장 큰 경우로, 재귀 호출보다 먼저 처리된다

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

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

탐욕 알고리즘(greedy algorithm)은 무엇을 합니까?

1. A재귀만 사용합니다
2. B가능한 모든 해를 시도합니다
3. C각 단계에서 지역적으로 가장 좋은 선택을 합니다
4. D항상 최적해를 제공합니다

O(n²) 알고리즘이 O(n³)이기도 하다고 말하는 것은 옳습니까?

1. A아니요, Big O는 함수의 정확한 증가율을 항상 나타내야 하기 때문에
2. B아니요, 큰 n에서 n³이 n²보다 작기 때문에
3. C예, 단 n이 100보다 작을 때만
4. D예, Big O는 상한이고 n²은 n³보다 빠르게 증가하지 않기 때문에

헬드-카프 동적 계획법 알고리즘은 외판원 문제를 정확히 풉니다. 도시가 n개일 때 실행 시간은 얼마입니까?

1. AO(2^n²)
2. BO(n!)
3. CO(n² 2ⁿ)
4. DO(n³)

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²)