C언어로 쉽게 풀어쓴 자료구조 [연습문제 1장]

swap (a, b) {
	temp ← a
    a ← b
    b ← temp
}

max (a, b) {
	if (a>b)
    	return a
    else
    	return b
}        

sum (n) {
	i ← 0
    
    while (n) {
    	i ← i+n
        n ← n-1
    }
    return i
}

4. 생략

5. 생략
   
   

6. n=2^t (t∈Z) 라고 가정하자.
   이렇게 되면 총 t번의 연산이 필요하고, t=log2(n) 이므로, O(log n)이 된다.

7. 1) 바깥 for문: 총 n 번의 연산이 수행된다
   2) 안쪽 for문: 6번 문제와 같으므로 log2(n) 번의 연산이 수행된다.
   따라서 바깥 for문 한번마다 안쪽 for문이 수행되므로 곱셈을 하면, O(nlogn) 이 된다.

8. f(n) = n²+10n+8 이고, g(n) = n² 일때,
   모든 n≥1 에 대하여 |f(n)|≤20|g(n)| 이므로, f(n) = O(g(n)) = O(n²) 이 된다.   ∴ (3)번

9.  (1)번

10. 입력의 개수 n이 t일때 = t² 이며, 2t일때= 4t² 이 된다. 즉 입력의 개수가 2배가 되면 실행시간은 4배가 된다. ∴ (3)번

11.  (2)번

12. O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(2ⁿ) < O(n!)

13. 입력의 개수 n에 대하여, n>0 이므로 양변을 n으로 나누면
    각각 30+4/n, n 이 된다.
    n = 30 일때) 각각 30+4/30 > 30 이고
    n = 31 일때) 30+4/31 < 31 이므로
    n ≥ 31 일때부터 30n+4 가 n² 보다 작은값을 갖게 된다.

14. n	수행시간
    2	2×1
    4	4×2
    8	8×3 (오차 -1)
    16	16×4 (오차 +1)
    32	32×5 (오차 -2)
    n	n×log2(n)

    따라서 시간복잡도는 O(nlogn) 으로 예측할 수 있다.

15. f(n) = 5n²+3 이고, g(n) = n² 일때,
    모든 n≥1 에 대하여 |f(n)|≤10|g(n)| 이므로, f(n) = O(g(n)) = O(n²) 이 된다.

16. f(n) = 6n²+3n 이고, g(n) = n 일때,
    모든 n≥n0 에 대하여 |f(n)|≤c|g(n)| 을 만족하는 두 상수 c와 n0가 존재하지 않는다.
    ∴ 6n²+3n이 O(n)이 될 수 없다.

17. (1) 최악: O(1), 최선: O(1) → n번째 숫자를 출력하기만 하면 된다.
    (2) 최악: O(n), 최선: O(n) → 최솟값을 찾기 위해서는 배열의 원소를 모두 탐색해보아야 한다. 단, 원소가 하나인 경우 그 값을 반환하면 되므로 최선의 시간복잡도는 O(1)이 될 수 있다.
    (3) 최악: O(n), 최선: O(n) → 배열의 총합이므로 원소를 모두 탐색해야한다. 단, 원소가 하나인 경우 그 값을 반환하면 되므로 최선의 시간복잡도는 O(1)이 될 수 있다.