두근두근 자료구조 1장 (자료구조와 알고리즘) 연습문제

다음 중 선형 자료구조로 볼 수 없는 것은?

3. 트리

 

동일한 문제를 해결하는 알고리즘 A, B, C, D의 시간 복잡도가 다음과 같이 계산되었다고 하자. n이 충분히 크다고 할 때, 실행 시간이 적은 것부터 순서대로 나열해보라.

A: O(n) B: O(n^2) C: O(nlogn) D: O(2^n)

A < C < B < D

 

시간 복잡도를 빅오 표기법으로 나타내면?

3. o(n^2)

 

3개의 숫자 중에서 가장 큰 수를 찾는 알고리즘을 흐름도로 작성해보자.

 

다음의 빅오표기법들을 실행시간이 적게 걸리는 것부터 나열하라.

o(1) < o(log n) < o(n) < o(n log n) < o(n^2) < o(2^n) < o(n!)

 

다음 코드의 시간 복잡도는 어떻게 되는가?

o(n^2)

 

다음 코드의 시간 복잡도는 어떻게 되는가?

o(log n)

 

다음 코드의 시간 복잡도는 어떻게 되는가?

o(1)

 

다음 알고리즘의 시간 복잡도를 n에 대한 함수로 나타내고, 빅오 표기법으로도 나타내어라.

o(log n)

 

배열에 정수가 들어있다고 가정하고 다음 작접의 최악의 시간 복잡도를 빅오 표기법으로 말하라.

1. 배열의 n번째 숫자를 화면에 출력한다 o(n)

2. 배열안의 숫자 중에서 최소값을 찾는다 o(n)

3. 배열의 모든 숫자를 더한다 o(n)