SICP 연습문제 2.60 친절한 풀이 | 이태화 아카이브

[utterances-bot]

SICP 연습문제 2.60 친절한 풀이 | 이태화 아카이브

집합의 중복을 없애지 않은 집합 연산 구현

https://studyingeugene.github.io/sicp/chapter-2/exercise-2-60/

[comolove]

안녕하세요 문제풀이 글들 잘 보고 있습니다
위 풀이에서 새로 만든 합집합과 교집합의 시간복잡도 부분에서 의문이 들었는데요.

교집합의 경우 element-of-set? 을 s1의 원소 개수만큼 실행하고, element-of-set? 은 해당 set의 원소 개수만큼 실행하므로 여전히 O(n^2) 이 아닌가 생각합니다.

또, 합집합의 경우 append 연산이 O(1) 이 아니지 않나 생각이 들었습니다.

마지막으로, 이 프로시저들이 유용한 경우는 원소 중복이 발생할경우 {1, 2, 3} 의 원소가 3개가 아닐 수 있으므로 O(n) 일지 O(2n) 일지 알 수 없기 때문에 입력값으로 중복없이 원소가 들어오는 경우에 유용하지 않을까 생각합니다

[studyingeugene]

안녕하세요 문제풀이 글들 잘 보고 있습니다 위 풀이에서 새로 만든 합집합과 교집합의 시간복잡도 부분에서 의문이 들었는데요.

교집합의 경우 element-of-set? 을 s1의 원소 개수만큼 실행하고, element-of-set? 은 해당 set의 원소 개수만큼 실행하므로 여전히 O(n^2) 이 아닌가 생각합니다.

또, 합집합의 경우 append 연산이 O(1) 이 아니지 않나 생각이 들었습니다.

마지막으로, 이 프로시저들이 유용한 경우는 원소 중복이 발생할경우 {1, 2, 3} 의 원소가 3개가 아닐 수 있으므로 O(n) 일지 O(2n) 일지 알 수 없기 때문에 입력값으로 중복없이 원소가 들어오는 경우에 유용하지 않을까 생각합니다

오.. 구구절절 맞는 말씀이십니다.
이거 부끄럽네요 ㅎㅎ