Интерполяционный многочлен в форме Ньютона, построенныйпо узламx0, x1, ..., xn ипринимающий в этих узлах значенияy0, y1, ..., yn,представляется формулойpn(x) = a0 + a1(x-x0) + a1(x-x0)(x-x1) + ... + an(x-x0)(x-x1)...(x-xn-1)
Пусть коэффициентыa0, a1, ..., anмногочлена pn(x)уже вычислены. Мы добавляем новый узел xn+1,значение в котором должно быть равно yn+1,и строим новый многочлен Ньютона pn+1(x)на единицу большей степени по узламx0, x1, ..., xn, xn+1и значениямy0, y1, ..., yn, yn+1.Сколько действий нужно выполнить, чтобы вычислить всекоэффициенты нового многочлена?
(Отметьте один правильный вариант ответа.)
Варианты ответа
O(n2).
O(1).
O(n). (Верный ответ)
O(n3).