[자료구조] 다항식 표현, 다항식 덧셈

다항식 추상 데이터 타입

순서 리스트

- 예시

• 요일
• 트럼프 카드 한 벌의 값
• 주차별 수업 날짜

 

- 리스트 형태: (\(a_{1}, a_{2}, ... , a_{n-1}\))

- 공백 리스트의 예: ( )

 

순서 리스트에 대한 연산

• 리스트 길이 n의 계산
• 리스트의 항목을 왼쪽에서 오른쪽(오른쪽에서 왼쪽)으로 읽기
• 리스트로부터 i번째 항목을 검색, 0≤i<n
• 리스트의 i번째 항목을 대체, 0≤i<n
• 리스트의 i번째 위치에 새 항목 삽입, 0≤i<n
  -> i, i+1, ... , n-1 항목 번호를 i+1, i+2, ... , n으로 만듦
• 리스트의 i번째 항목을 제거 0≤i<n
  -> i, i+1, ... , n-1 항목 번호를 i-1, i-2, ... , n-2으로 만듦

 

순서리스트의 일반적인 구현

- 배열을 이용

- 문제접: 삽입, 삭제 시 오버헤드

 

다항식(polynomial)

\(a(x) = 3x^{2} + 2x - 4, b(x) = x^{8} - 10x^{5} - 3x^{3} + 1\)

- 계수(coefficient): 3, 2, -4

- 지수(exponent): 2, 1, 0

- 차수(degree): 0이 아닌 제일 큰 지수

 

다항식의 합과 곱

\(a(x) + b(x) = \sum(a_{i} + b_{i})x^{i}\)

\(a(x) \times b(x) = \sum(a_{i}x^{i} \times \sum(b_{i}x^{i}))\)

 

구현

class Term 
{ // 다항식의 계수와 지수의 정보를 담는 클래스
    friend class Polynomial;

private:
    float coef; // 계수
    int exp;    // 지수
};

class Polynomial
{ // 다항식 클래스
private:
    Term *termArray; // 0이 아닌 항의 배열
    int capacity;    // termArray의 크기
    int terms;       // 0이 아닌 항의 수

public:
    Polynomial();
    // 다항식 초기화

    Polynomial Add(Polynomial poly);
    // *this 다항식과 인자로 전달받은 다항식의 합을 리턴

    Polynomial Mult(Polynomial poly);
    // *this 다항식과 인자로 전달받은 다항식의 곱을 리턴

    float Eval(float f);
    // *this 다항식의 f에서의 값을 리턴

    void NewTerm(const float, const int);
    // 새로운 항을 termArray끝에 첨가
};

다항식 배열은 차수가 작은 순서대로 저장한다.

 

다항식 덧셈

함수 Add: a(x)(*this)와 b(x)를 항별로 더하여 c(x)를 만드는 함수

-> Polynomial의 디폴트 생성자가 capacity와 terms를 각각 1, 0으로 초기화한다고 가정

Polynomial Polynomial::Add(Polynomial b)
{
    Polynomial c; // 리턴할 다항식
    int aPos = 0, bPos = 0; // 다항식 a, b에서 작업할 부분(n차항)
    while ((aPos < terms) && (bPos < b.terms)) 
    // a, b의 배열 중 한쪽이 전부 더해질 때까지 작업 반복
        if (termArray[aPos].exp == b.termArray[bPos].exp) 
        { // 작업할 항의 차수가 같은 경우
            float t = termArray[aPos].coef + b.termArray[bPos].coef;
            // 차수가 같으므로 계수끼리 덧셈         
            if (t)                                 // 계수가 0이 아니라면
                c.NewTerm(t, termArray[aPos].exp); // 리턴할 다항식에 작업한 차수의 항 추가
            aPos++; // 작업할 부분 이동
            bPos++; // 작업할 부분 이동
        }
        else if (termArray[aPos].exp < b.termArray[bPos].exp)
        {
            c.NewTerm(b.termArray[bPos].coef, b.termArray[bPos].exp);
            bPos++;
        }
        else
        {
            c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
            aPos++;
        }
        // 작업할 다항식의 차수를 비교해 차수가 작은쪽의 항을 리턴할 다항식에 추가

    for (; aPos < terms; aPos++)
        c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
    for (; bPos < b.terms; bPos++)
        c.NewTerm(b.termArray[bPos].coef, b.termArray[bPos].exp);
    // a, b 다항식 중 한쪽 다항식을 전부 작업했으므로
    // 남은 다항식을 리턴할 다항식에 전부 추가
    return c;
};

void Polynomial::NewTerm(const float theCoef, const int theExp)
{ // 새로운 항을 termArray 끝에 첨가
    if (terms == capacity) // 배열이 가득 채워졌을 경우
    {                      // 배열의 크기를 2배로 확장
        capacity *= 2; 
        Term *temp = new Term[capacity]; // 새로운 배열 생성
        copy(termArray, termArray + terms, temp);
        delete[] termArray; // 그전 메모리를 반환
        termArray = temp;
    }
    termArray[terms].coef = theCoef;
    termArray[terms++].exp = theExp;
    // 새로운 항 termArray 끝에 첨가
}

시간복잡도 - O(m+n)

 

Add의 시간복잡도

1. Add 함수가 종료될 때 c.capacity가 \(2^{k}\) 가정
2. 총 \(2^{0}+2^{1}+2^{2}+...+2^{k-1}=2^{k}-1\) 만큼 복사
3. \(2^{k}-1<c.term\) (마지막 복사된 수보다 현재 항 수가 큼)
4. \(c.term ≤ m+n\) (두 다항식의 합은 \(m+n\) 보다 항 수가 적거나 같음)
5. 따라서 \(2^{k}-1<m+n\)
6. 양변에 2를 곱하고 -1을 함
7. \(2^{k}-1\)(복사된 수) \(< 2(m+n)-1\)
8. 따라서 \(2^{k}-1=O(m+n)\)