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

재귀란 무엇입니까?

1. A절대 끝나지 않는 루프
2. B자료 구조의 한 종류
3. C정렬 방법의 하나
4. D더 작은 입력에 대해 자기 자신을 호출하는 함수

O(n) 알고리즘이 n = 100만에서 3초 걸립니다. n = 200만에서는 대략 얼마나 걸립니까?

1. A6초
2. B9초
3. C12초
4. D3초

3n² + 5n + 2의 Big O는 무엇입니까?

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

분할 상환 분석(amortised analysis)은 무엇을 측정합니까?

1. A최선의 입력에서 알고리즘의 비용
2. B무작위 입력에 대한 기대 비용
3. C연산열 전체에서 가장 비싼 단일 연산 하나의 비용
4. D최악의 연산 순서에 걸친 연산당 평균 비용

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

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

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

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

어떤 배낭 문제 변형에서 탐욕적 규칙 "무게당 가치 순으로 물건 담기"가 항상 최적의 답을 줍니까?

1. A두 변형 모두
2. B어느 변형도 아님
3. C물건을 통째로만 담아야 하는 0/1 배낭 문제
4. D물건을 나눌 수 있는 분할 가능 배낭 문제

단일 연결 리스트에서 이진 탐색이 O(log n) 시간을 주지 못하는 이유는 무엇입니까?

1. A직접 인덱스 접근이 없으므로 가운데 원소에 도달하는 데 O(n) 단계가 걸리기 때문에
2. B연결 리스트 노드의 비교가 더 느리기 때문에
3. C이진 탐색에는 최소 두 배의 메모리가 필요하기 때문에
4. D연결 리스트는 정렬할 수 없기 때문에