Report #3- 문제 1 Set(집합) 추상 데이터 타입을 정의하고, 다음과 같은 연산자들을 포함시켜라. 여기서 S, S1, S2는 집합을 나타내고, i는 집합 원소를 나타낸다. 연산 의미 create() Return {} insert(S, i) If i є S then.

Presentation on theme: "Report #3- 문제 1 Set(집합) 추상 데이터 타입을 정의하고, 다음과 같은 연산자들을 포함시켜라. 여기서 S, S1, S2는 집합을 나타내고, i는 집합 원소를 나타낸다. 연산 의미 create() Return {} insert(S, i) If i є S then."— Presentation transcript:

1 Report #3- 문제 1 Set(집합) 추상 데이터 타입을 정의하고, 다음과 같은 연산자들을 포함시켜라. 여기서 S, S1, S2는 집합을 나타내고, i는 집합 원소를 나타낸다. 연산 의미 create() Return {} insert(S, i) If i є S then return S Else return S U {i} remove(S, i) return S – {i}

2 Report #3- 문제 1 연산 의미 is_in(S, i) If i є S then return true Else
return false End if union(S1, S2) If S2 = Φ then return S1 for each i є S2 do S1 <- insert(S1, i) repeat

3 Report #3- 문제 1 연산 의미 difference(S1, S2) If S2 = Φ then return S1 Else
for each iє S2 do S1 <- remove(S1, i) repeat End if

4 Report #3- 문제 1 연산 의미 intersection(S1, S2) S <- create()
for each iє S1 do if iє S2 then S <- insert(S, i) end if repeat return S

5 Report #3- 문제 2 알고리즘 T(n) = 3*(n-1) (∵ T(n)을 빅오 표기법으로 표현하면 O(nlog2n)
안쪽 루프의 본체 연산은 비교 1번, 할당 1번, 덧셈 1번으로 총 3개의 연산 수행 안쪽 루프의 반복 회수는 log2(n-1) (왜냐면, 반복시 제어변수 j의 값은 두배가 되고, k번 반복시 그 값은 2k이고, 이 값이 2k = (n-1)이 될 때 반복은 종료된다. 여기서 k = log2(n-1)이 되므로, 안쪽 루프의 반복 회수는 log2(n-1)이다. 바깥쪽 루프의 반복 회수는 n -1 바깥쪽 루프의 각 반복에 대해서 안쪽 루프가 log2(-1)n 반복되고, 안쪽 루프의 본체의 연산 회수가 3이므로, 총 연산 회수는 3*(n-1)log2(n-1)이 된다.) T(n)을 빅오 표기법으로 표현하면 O(nlog2n) for (i = 1; I <n; i++) do for (j = 1; j <n; j *= 2) do if (a[i] > b[j]) sum += a[i]; end if repeat

6 평가 기준 각 문제의 배점은 5점씩 각 문제에서 2 또는 3점 감점
문제 2에서, T(n) 기술시 그 이유를 설명하지 않으면 -3