ADT (Abstract Data Type, 추상 자료형) : 다항식 추상 자료 구현

The Array (배열)

메모리 공간의 연속적인 집합 

배열은 인덱스, 값 두 가지가 쌍으로 이루어진 집합으로 구현되어 있다.

C++에서 array는 인덱스 0부터 시작하며, 배열의 범위 밖을 접근할 수 없다.

자료형과 변수 이름, 크기로 입력할 수 있다.

 

다항식 추상 자료를 구현해보자

리스트의 operations

 

1. 리스트의 길이 N을 찾아라

2. 한 쪽에서 다른 쪽 끝까지 읽어라 (양방향)

3. i번째 특정 요소를 검색해라

4. i번째 공간에 새로운 값을 저장해라

5. 0과 N번째 사이 특정 위치에 새로운 요소를 삽입해라, (길이도 1 늘어남)

6. 0과 N번째 사이특정 위치에 요소를 삭제해라 (길이가 1 줄어듬)

 

list를 array로 구현하면 삽입과 제거이 비효율적. 오버헤드 발생

 

다항식 분석

계수, 지수, 변수로 나누어보자.

 

다항식 자료구조 구현 1

다항식의 클래스의 private의 멤버.

degree : 최고 차수

coef : 계수 배열 /최고 차수 길이의 배열을 만듬.

MaxDegree : 최고 차수를 지정해준다.

a는 다항식 클래스의 객체이다. n은 최고

지수가 감소하는 순서로 계수는 저장됬다. coef 배열에는 해당 지수에서 인덱스만큼을 뺀 값이 저장되는 것 같다.

이는 많은 다항식 간단한 다항식 연산을 수행할 수 있다. 합과 차, 곱 등

MaxDegree 이상의 지수를 가진 데이터를 저장할 수 없고, 많은 메모리가 낭비된다.

 

다항식 자료구조 구현 2 (개선 1)

coef를 포인터 변수로 지정해준다.

degree (최고 차수)의 값을 입력 받는 polynomial의 생성자를 만들어준다.

degree의 최고 차수 +1 길이의 배열을 메모리에 할당한다.  index를 exponent로 활용하고 계수를 저장

이 경우 다항식이 매우 sparse할 경우 메모리 공간이 낭비된다. (x**1000 만 있을 경우 1000의 메모리 공간이 낭비 됨.)

 

다항식 자료구조 구현 3 (개선 2)

모든 다항식을 termArray를 사용해서 표현하는 방식

각 termArray의 요소는 term type이다. (term 클래스 구현 필요)

 

 

두개의 클래스로 이루어져 있다. 메모리 낭비가 없는 것이 장점. termArray의 size(필요 메모리)와 term (항의 개수)

 

다항식 추가

 

a(x) + b(x) = c(x)

두 지수를 비교해서 두개의 다항식을 합병하는 것이 일반적인 방식.

두 지수 사이의 관계와 적절한 동작을 수행하는지 시험해봐야 함.

 

terms과 capacity의 크기가 같아지면 길이를 두배로 늘려줌.

copy 함수에 원본 시작 iterator, 원본 끝 iterator, 특정 시작 iterator를 넣어주면 특정 iterator에 복사를 할 수 있다.

(termarray에 tems(다항식의 개수)를 더해주면 원본 끝 iterator가 됨.)

termarray에 terms(다항식의 개수)를 입력. term 객체의 계수와 지수를 저장

 

분석

O(m+n) m과 n의 개수 (두 다항식의 합의 개수)에 따라서 시간 소요.

배열을 두배로 만드는 것은 전체 실행시간에 상수로 취급됨. 다르게 말하면 배열을 두배로 만드는 것은 전체 실행 시간의 매우 작은 부분임.

다항식 a는 a.start부터 a.finish까지의 n개의 0아 아닌 항을 갖는다. (a.finish는 a.start+n-1임)

만일 어떤 항도 갖지 않고 있다면 a.finish = a.start-1이 된다.

 

직접 구현은 직접해보자 ㅎㅎ