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

순서가 잘못된 인접 원소를 반복적으로 교환하는 정렬 알고리즘은 무엇입니까?

1. A퀵 정렬(Quicksort)
2. B힙 정렬(Heap sort)
3. C병합 정렬(Merge sort)
4. D버블 정렬(Bubble sort)

이미 정렬된 배열에서 삽입 정렬의 최선의 경우 시간 복잡도는 무엇입니까?

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

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

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

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

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

원소가 1,000,000개인 정렬된 배열에서 이진 탐색은 최악의 경우 대략 몇 번 비교합니까?

1. A약 20
2. B약 1,000
3. C약 500,000
4. D약 100

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

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

결정 불가능한 문제와 다루기 어려운 문제의 차이는 무엇입니까?

1. A결정 불가능한 문제는 모든 입력에 대한 알고리즘이 없고, 다루기 어려운 문제는 알고리즘이 있지만 너무 느리다
2. B다루기 어려운 문제는 어떤 알고리즘으로도 풀 수 없고, 결정 불가능한 문제는 지수 시간만 있으면 된다
3. C결정 불가능한 문제는 NP에, 다루기 어려운 문제는 P에 속한다
4. D둘 다 그 문제에 알고리즘이 전혀 없다는 뜻이다

클래스 NP의 올바른 정의는 무엇입니까?

1. A다항이 아닌 문제
2. B인증서가 주어지면 "예" 답을 다항 시간에 검증할 수 있는 결정 문제
3. C어떤 알고리즘으로도 풀 수 없는 문제
4. D다항 시간에 풀 수 없는 문제