[17p]
1. 알고리즘
2. 의사 코드 (pseudo-code)
3. 반복성
[21p]
1. 연산
2. 추상
[35p]
1. O(n^2)
2. O(n!)
3. O(n^2)
∵ n^2 > nlog2n
4. O(n^2)
∵ n^2 + (n-1)^2 + (n-2)^2 + ... + 1 이므로
2차항의 계수와 관계없이 최고차항인 n^2가 빅 오에 해당.
[36-37p 연습문제]
1.
exchange(a, b):
tmp <- a
a <- b
b <- tmp
2.
bigger(a,b):
if a > b then
return a
else
return b
3.
add(n):
for i<-1 to n do
sum += i
return sum
4.
Create: 집합을 생성하고 반환한다.
Insert: 집합에 원소를 추가한다.
Remove: 집합에 원소를 제거한다.
Is_In: 집합에 해당 원소가 있는지 확인한다.
Union: 두 집합의 합집합을 구한다.
Intersection: 두 집합의 교집합을 구한다.
Difference: 두 집합의 차집합을 구한다.
5.
Boolean And(x,y) ::= if a == 1 and b == 1 then return 1
else return 0
Boolean Or(x,y) ::= if a == 1 or b == 1 then return 1
else return 0
Boolean Not(x) ::= if x == 1 then return 0
else return 1
Boolean Xor(x) ::= if a == 1 or b == 0 then return 1
if a == 0 or b == 1 then return 1
else return 1
6.
루프만이 존재하는 코드.
만약에 n = 32이라면, 1, 2, 4, 8, 16까지 총 5번 실행됨.
f(32) = 5를 만족하는 식은 log2(5). 즉 f(x) = log2(n).
O(log2(n))
7.
위에서 언급한 log2(n)이 j로 들어가있고
i는 반복에만 관심 있음. n = 5라면 5번 반복하는 꼴. (n번)
그러므로 n인데, log2(n)도 차수이므로,
O(nlog2(n))
8.
가장 큰 차수를 계수없이 표기하므로
답은 3번 O(n^2)
9.
정답은 1번 연산의 횟수.
프로그램의 수행시간과는 당연히 관계없음.
메모리 양과도 상관 없음.
입력 데이터는 n 그 자체이다.
10.
단순히 n이 1에서 2로 2배 증가했다고 가정하면,
반면 n^2은 1 -> 4이므로 4배 증가한 것이다.
답은 3번 4배.
11.
답은 3번 빅세타.
12.
13.
근이 30.13이므로 정수로는 31부터 30n+4가 n^2보다 작은 값을 가진다.
| 30n+4 | n^2 | |
| n=29 | 874 | 841 |
| n=30 | 904 | 900 |
| n=30.132746 | 907.98238 | 907.98238(소수점 6자리 반올림) |
| n=31 | 934 | 961 |
14.
| 실제 수행시간 | 계산 | |
| n = 2 | 2 | 2 |
| n = 4 | 8 | 8 |
| n = 8 | 25 | 24 |
| n = 16 | 63 | 64 |
| n = 32 | 162 | 160 |
n = 8, 16, 32일때는 약간 오차가 있긴 하지만 감안하자. (이론과 실제 실습의 차)
15.
일 때 이므로
(1) 최선: , 최악:
(2) 최선: , 최악:
(3) 최선: , 최악: