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

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

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

O(2ⁿ) 증가를 무엇이라고 합니까?

1. A선형
2. B다항
3. C로그
4. D지수

어떤 연산이 O(1) 시간에 실행된다는 것은 무엇을 의미합니까?

1. A실행 시간 1초마다 정확히 원소 하나를 처리한다
2. B한 번만 실행할 수 있다
3. C항상 정확히 1초가 걸린다
4. D실행 시간이 입력 크기에 따라 증가하지 않는다

밑이 k이고 자릿수가 d인 정수 n개에 대한 LSD 기수 정렬의 실행 시간은 얼마입니까?

1. AO(d(n + k))
2. BO(n log n)
3. CO(dn log k)
4. DO(n²)

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

1. AO(log n)
2. BO(n log n)
3. CO(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무방향 그래프에서만 동작하기 때문에
2. B정점은 추출될 때 확정되지만, 나중의 음수 간선이 여전히 더 짧은 경로를 줄 수 있기 때문에
3. C음수 간선마다 무한 루프에 빠지기 때문에
4. D우선순위 큐에 음수를 저장할 수 없기 때문에

큰 n에서 n!과 2ⁿ은 어떻게 비교됩니까?

1. A같은 비율로 증가한다
2. Bn!은 O(n²)이다
3. C2ⁿ이 n!보다 빠르게 증가한다
4. Dn!이 2ⁿ보다 빠르게 증가한다