2-3강 - Polynomials (다항식)

4. Polynomials

cf> array는 그 자체로 [1]자료 구조이며 [2]또다른 ADT 구현할 수 있다. 

1) ADT - ordered list(linear list)

0> 예시 (4번째 예시처럼 공백 리스트도 있다.

- 일주일의 요일들: (일요일, 월요일, 화요일, 수요일, 목요일, 금요일, 토요일)

- 건물의 층 : (지하, 로비, 일층, 이층)

- 미국의 제2차 세계대전 참전 연도 : (1941, 1942, 1943, 1944, 1945)

​- 스위스의 제2차 세계대전 참전 연도 : ( ) 

 

1> Object

- object : a set of ordered pairs of <e_i, a_i> (전제: a_i는 계수, e_i는 지수, e_i는 0이상의 정수)

(사실 sum of terms이다.)

 

2> function

- 리스트의 길이 계산

- 리스트를 왼쪽부터 오른쪽으로 읽기 (혹은 반대 순서로 읽기)

- i번째 항목 검색, 대체, 삽입, 제거

3> 보편적인 구현 방법  (Sequential mapping)

- array에 저장 <index(i)와 list element(item_i)를 대응>

- Sequential mapping : item_i, item_i+1이 연속적인 index i, i+1에 저장되어서

(4단원에서 Nonsequential mapping을 다룰 것)

 

2) Polynomial Representation

1> 첫 번째 방법 : dense representation

#define MAX_DEGREE 101 /* 다항식의 최대 차수 + 1 */

typedef struct {                                                        
	int degree;                     
	float coef[MAX_DEGREE];
} polynomial; 

- degree: 해당 다항식의 차수

- coef: 다항식의 계수들

- 지수들은 내림차순 정돈

- 지수가 n-i인 항이 있으면, x^(n-i)의 계수는 a.coef[i]이거나 a.coef[i]=0 (a는 polynomial type이다.)

- 단점: a.degree가 MAX_DEGREE보다 많이 작으면 메모리 낭비

 

cf> dense representation으로 나타낸 ADT

- object : a set of ordered pairs of <e_i, a_i> (전제: a_i는 계수, e_i는 지수, e_i는 0이상의 정수)

(사실 sum of terms이다.)

- function

- 예제

 

2> 두 번째 방법 : sparse representation

(공간 절약)

#define MAX_TERMS 100 /* 배열 terms의 크기 */

typedef struct {                                     
	float coef;  
	int expon;  
} polynomial;  

polynomial terms[MAX_TERMS];              
int avail = 0;   

- 0이 아닌 항의 수가 MAX_TERMS를 초과하지 않는다면

- TERMS 내부에 2개 이상의 다항식을 담을 수 있다.

- 장점 : 다항식에 0인 항이 많을 때, 메모리를 낭비하지 않을 수 있다.

- 단점 : 다항식의 모든 항이 0이 아닐 때, 구조체를 여러개 만드므로(구조체 배열) 거의 2배의 기억 공간을 필요로 한다.

(모든 항이 0이 아닌 경우 1번에서는 int 하나에 float array, 2번에서는 int와 float이 쌍인 구조체 array)

 

3) Polynomial addition

1> 2개의 polynomial을 더하는 함수

void padd (int starta, int finisha, int startb, int finishb, int *startd, int *finishd)

{
	/*add A(x) and B(x) to obtain D(x)*/
	float coefficient;
	*startd = avail;
	while (starta <= finisha && startb <= finishb)
	{
		switch (COMPARE(terms[starta].expon, terms[startb].expon))
		{
		case -1:/* a expon < b expon */
			attach(terms[startb].coef, terms[startb].expon);
			startb++;
			break;
		case 0:
			coefficient = terms[starta].coef + terms[startb].coef;
			if (coefficient)
			{
				attach(coefficient, terms[starta].expon);
			}
			starta++;
			startb++;
			break;
		case 1: /*a expon > b expon*/
			attach(terms[starta].coef, terms[starta].expon);
		}
		/* add in remaining terms of A(x)*/
		for (; starta <= finisha; starta++)
			attach(terms[starta].coef, terms[starta].expon);
		/* add in remaining terms of B(x)*/
		for (; startb <= finishb; startb++)
			attach(terms[startb].coef, terms[startb].expon);
		*finishd = avail - 1;
	}
}

- 시간 복잡도 O(n+m) (n과 m은 각각 A와 B의 항의 개수)

 

2> 새로운 항을 더해가는 형태

void attach(float coefficient, int exponent)
{
	/* add a new term to the polynomial*/
	if (avail >= MAX_TERMS) 
	{
		fprintf(stderr, "Too many terms in the polynomial");
		exit(1);
	}
	
	terms[avail].coef = coefficient;
	terms[avail++].expon = exponent;
}