NTP

14. Sabiranje/Oduzimanje/Mnozenje polinoma

p(x) = a[n] * x^n + a[n-1] * x^(n-1) + a[n-2]*x^(n-2) + … + a[1]*x + a[0]
q(x) = b[m] * x^m + b[m-1] * x^(m-1) + b[m-2]*x^(m-2) + … + b[1]*x + b[0]
p(x) = 4*x^3 + 7*x^2 – 3*x + 2
q(x) = 5*x^2 +3*x + 4
r(x) = p(x) + q(x) = 4*x^3 + 12*x^2 + 6
———————————————

int saberiPol(int n, double a[], int m, double b[], double c[]) {
  int mn = min(n, m)
  int mx = max(m, n);
  for (k = 0; k <= mn; k++)
    c[k] = a[k] + b[k];
  if (n > m) {
    for (k = mn+1; k <= n; k++)
  c[k] = a[k];
  } else {
    for (k = mn+1; k <= m; k++)
  c[k] = b[k];
  }
  while ((mx > 0) && (c[mx] == 0))
    mx–;
  return mx;
}
——————————————–

Slozenost je O(max(n,m)), Neko pise i O(m+n)
p(x) = 4*x^3 + 7*x^2 – 3*x + 2
q(x) = -4*x^3 -7*x^2 + 5*x + 4
r(x) = 0*x^3` + 0*x^2 + 2*x + 6
———————————————

int oduzmiPol(int n, double a[], int m, double b[], double c[]) {
  int mn = min(n, m)
  int mx = max(m, n);
  for (k = 0; k <= mn; k++)
    c[k] = a[k] – b[k];
  if (n > m) {
    for (k = mn+1; k <= n; k++)
  c[k] = a[k];
  } else {
    for (k = mn+1; k <= m; k++)
  c[k] = -b[k];
  }
  while ((mx > 0) && (c[mx] == 0))
    mx–;
  return mx;
}
——————————————–

Ako je stepen polinoma p(x) jednak n, a stepen polinoma q(x) je m,
onda je stepen proizvoda n+m
a[i]*x^i * b[j]*x^j —> a[i] * b[j] * x^(i+j)
a[i+1]*x^(i+1) * b[j-1]*x^(j-1) —> a[i+1] * b[j-1] * x^(i+j)
———————————————

int pomnoziPol(int n, double a[], int m, double b[], double c[]) {
  int mn = m + n;
  for (k = 0; k <= mn; k++)
    c[k] = 0;
  for (i = 0; i <= n; i++)
    for (j = 0; j <= m; j++) // mnozimo a[i]*x^i i b[j]*x^j —> a[i] * b[j] * x^(i+j)
  c[i+j] = c[i+j] + a[i] * b[j]
  return mn;
}
——————————————–

O(n*m)