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

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

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

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

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

무차별 대입(brute-force) 알고리즘이란 무엇입니까?

1. A가능한 모든 후보 해를 시도하는 알고리즘
2. B여러 프로세서에서 실행되는 알고리즘
3. C항상 재귀를 사용하는 알고리즘
4. D무작위로 답을 추측하는 알고리즘

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

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

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

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

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

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

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

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

삽입 정렬은 정렬된 입력에서 O(n)에 실행됩니다. 이것은 비교 정렬의 Ω(n log n) 하한과 모순됩니까?

1. A아니요, 삽입 정렬은 비교 정렬이 아니기 때문에
2. B아니요, 하한은 모든 입력이 아니라 모든 입력에 걸친 최악의 경우에 적용된다
3. C예, 단 길이가 100보다 짧은 배열에서만
4. D예, 따라서 하한이 틀렸다