[알기쉬운 알고리즘] 2장 연습문제

알기쉬운 알고리즘 2장 연습문제를 공부한 내용을 정리하였습니다. 틀린 점이나 피드백이 있으시다면 언제든지 답글로 달아주시면 감사하겠습니다.

 

1. 360과 96의 최대공약수를 나눗셈을 이용한 유클리드 알고리즘으로 구하라.

G(A, B) = G(B, R) 이다. ( A / B = 몫....R(나머지) )

G(360, 96) = G(96, 72)

G(96, 72) = G(72, 24)

G(72, 24) = G(24, 0) = 24

 

따라서 360 과 96의 최대공약수는 24이다.

 

2. 유클리드의 최대공약수 mod 연산 알고리즘의 시간복잡도를 O-표기로 표현하라.

Euclid(a, b)
입력 : 정수 a,b; 단 a >= b >= 0
출력 : 최대공약수(a, b)
if (b == 0) return a
return Euclid(b, a mod b)

O(logn), a % b 를 통해 결국 0에 이르게 되는데, 나머지는 나눈 값보다 작기 때문에(b > r) 빠르게 감소하는 것을 알 수있다. 직관을 통해서 log적으로 연산이 줄어들겠다는 것을 파악할 수 있다. 정확한 증명은 귀납법을 통해 증명해야 하므로 패스.

17. 최대 숫자 찾기 알고리즘의 시간복잡도를 구하라. 단, n개의 숫자가 있다고 가정하라.

O(n), max 값을 통해서 현재까지 탐색한 숫자 중 가장 큰 숫자와 새로운 숫자를 비교하는데, n 개의 숫자의 경우 n-1 번 비교해야 하므로 O(n)이라고 할 수 있다.

 

18. 임의의 숫자를 찾기 위한 순차탐색의 최악 경우 시간복잡도를 구하라. 단, n개의 숫자가 있다고 가정하라.

O(n),n개의 숫자가 늘어서 있을 때 최악의 경우 가장 마지막인 n번째에 숫자가 있다. 따라서 비교횟수를 약 n번 진행하므로 O(n)이다.

19. 임의의 숫자를 찾기 위한 순차탐색의 평균 경우 시간복잡도를 구하라. 단, n개의 숫자가 있다고 가정하라.

평균 경우의 시간복잡도는 모든 경우의 시간복잡도의 평균이라고 할 수 있다. 

비교횟수가 1 ... n-1 까지이며, 이에 대한 평균이므로 ∑k 라고 할 수 있다.

즉, n(n-1) / 2 이고, 이것을 n개로 나누게 되면 약 n / 2 이다. 

원하는 수를 찾지 못하는 경우도 있을 수 있는데, 이 경우 n회의 탐색을 진행하기 때문에 ( n + n / 2 ) / 2 = 0.75n 정도가 나온다.

따라서 평균 경우의 시간복잡도는 O(n)이다.

20. 임의의 숫자를 찾기 위한 순차탐색의 최선 경우 시간복잡도를 구하라. 단, n개의 숫자가 있다고 가정하라.

순차탐색의 가장 앞에 있을 경우에 바로 찾을 수 있으므로 최선의 경우는 Θ(1) 이다.

 

21. n개의 정렬된 숫자에서 임의의 숫자를 찾기 위한 보간탐색의 최악의 경우 시간복잡도를 구하여라.

최악 : O(n)

22. n개의 정렬된 숫자에서 임의의 숫자를 찾기 위한 보간탐색의 최선/평균의 경우 시간복잡도를 구하여라.

평균 : O(log(logn))

최선 : Θ(1)

23. n개의 정렬된 숫자에서 임의의 숫자를 찾기 위한 이진탐색의 최악의 경우 시간복잡도를 구하여라.

최악 : O(logn)

24. n개의 정렬된 숫자에서 임의의 숫자를 찾기 위한 이진탐색 알고리즘의 평균 경우 시간복잡도를 구하여라.

 

25. 한붓그리기 알고리즘의 최악 경우 시간복잡도를 구하라. 단, 그래프의 정점의 수는 n이고, 선분의 수는 m이다.

최악 : O(m * n)

26. 다음의 함수를 각각 O-표기로 나타내라.

10000, O(1)

4logn-9, O(logn)

6n-1000, O(n)

2nlogn+3n+logn-7, O(nlogn)

5n^2+9n-15, O(n^2)

3n^3+5n-7n+16, O(n^3)

6n^9+2n^7-n^6+2n+1, O(n^9)

2^n+n^15+n^4-3, O(2^n)

 

 

2^n+n^15+n^4-3, 이 식의 O-표기에서 관건은 2^n 과 n^15 중 최고차항을 가리는 일이다.

 

n = 1000000 이라고 가정할 때(10^6),

각각, 2^(10^6) (10^6)^15 을 가진다.

log를 씌워 비교를 해보면

log(10^6)^15 = log10^90 = 90

log2^(10^6) = 10^6 * log2 = 10^6 * 0.3 (log2를 약 0.3으로 가정)

 

90 < 10^6 * 0.3 보다 압도적으로 작으므로 2^n이 n^15보다 더 큰 차수라는 것을 알 수 있다.^^