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

증가율의 상한(upper bound)을 나타내는 표기법은 무엇입니까?

1. ABig Theta
2. BBig O
3. CLittle omega
4. DBig Omega

선택 정렬(selection sort)은 어떻게 동작합니까?

1. A정렬되지 않은 부분의 최솟값을 반복해서 찾아 앞으로 교환한다
2. B각 원소를 이동시키며 커지는 정렬된 부분에 삽입한다
3. C배열을 절반으로 나눈 뒤 병합한다
4. D순서가 잘못된 이웃 원소들을 반복해서 교환한다

n개의 수로 된 정렬되지 않은 배열에서 가장 큰 값을 찾는 시간 복잡도는 무엇입니까?

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

길이가 m과 n인 문자열의 최장 공통 부분 수열에 대한 표준 동적 계획법 알고리즘의 시간 복잡도는 무엇입니까?

1. AO(m + n)
2. BO(mn)
3. CO(2^m+n)
4. DO(mn log n)

퀵 정렬의 최악의 경우 시간 복잡도는 무엇입니까?

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

도달 가능한 기저 사례가 없는 재귀 함수에 대한 진술 중 옳은 것은 무엇입니까?

1. A자동으로 0을 반환한다
2. B컴파일러가 항상 안전하게 끝나는 루프로 바꾼다
3. C호출 스택이 넘칠 때까지 계속 자신을 호출한다
4. DO(1) 시간에 실행된다

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

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

최단 단순 경로는 다항 시간에 찾을 수 있습니다. 일반 그래프에서 두 정점 사이의 최장 단순 경로를 찾는 것에 대해 알려진 것은 무엇입니까?

1. A가중치를 음수로 바꾼 다익스트라 알고리즘으로 풀 수 있다
2. B항상 O(V + E)에 풀 수 있다
3. C결정 불가능하다
4. DNP-hard이다