Вычислить временную сложность алгоритма

Итак, вот алгоритм, который должен возвращать полиномиальное значение P(x) данного полинома с любым заданным x.

A [] - массив коэффициентов, а P[] - степень массива x.

(например, x^2 +2*x + 1 будет иметь: A[] = {1,2,1}, P[]= {2,1,0})

Также recPower() = O(logn)

int polynomial(int x, int A[], int P[], int l, int r)
{
    if (r - l == 1)
        return ( A[l] * recPower(x, P[l]) ) + ( A[r] * recPower (x, P[r]) );
    int m = (l + r) / 2;
    return polynomial(x, A, P, l, m) + polynomial(x, A, P, m, r);
}

Как мне рассчитать сложность этого времени? Я озадачен из-за заявления if. Я понятия не имею, каким будет отношение повторения.

Источник

2 ответа

Решение

Следующее наблюдение может помочь: как только мы r = l + 1, мы тратим O(logn) время и все готово.

Мой ответ требует хорошего понимания дерева рекурсии. Так что действуйте с умом.

Итак, наша цель - найти: через сколько итераций мы сможем сказать, что у нас r = l + 1?

Давайте разберемся:

Сфокусироваться на return polynomial(x, A, P, l, m) + polynomial(x, A, P, m, r);

Давайте сначала рассмотрим левую функцию polynomial(x, A, P, l, m), Главное, что следует отметить l, остается неизменным во всех последующих левых функциях, вызываемых рекурсивно.

Под левой функцией я подразумеваю polynomial(x, A, P, l, m) и под правильной функцией я имею в виду

polynomial(x, A, P, m, r),

Для левой функции polynomial(x, A, P, l, m), У нас есть:

Первая итерация

l = l and r = (l + r)/2

Вторая итерация

l = l and r = (l + (l + r)/2)/2

Который означает, что

r = (2l + l + r)/2

Третья итерация

l = l and r = (l + (l + (l + r)/2)/2)/2

Который означает, что

r = (4l + 2l + l + r)/4

Четвертая итерация

l = l and r = (l + (l + (l + (l + r)/2)/2)/2)/2

Который означает, что

r = (8l + 4l + 2l + l + r)/8

Это означает, что в n-й итерации мы имеем:

r = (l(1 + 2 + 4 + 8 +......2^n-1) + r)/2^n

и завершающее условие r = l + 1

Решение (l(1 + 2 + 4 + 8 +......2^n-1) + r)/2^n = l + 1, мы получаем

2^n = r - l

Это означает, что n = log(r - l), Можно сказать, что во всех последующих вызовах левой функции мы игнорировали другой вызов, то есть вызов правой функции. Причина в следующем:

Так как в правильном вызове функции мы l = mгде m уже приведено, как мы берем среднее, и r = r, что еще более усреднено, это асимптотически не повлияет на сложность времени.

Таким образом, наше дерево рекурсии будет иметь максимальную глубину = log (r - l). Это правда, что не все уровни будут полностью заполнены, но для простоты мы предполагаем это в асимптотическом анализе. Так что после достижения глубины log(r - l)мы называем функцию recPower, который занимает O(logn) время. Общее количество узлов (при условии, что все уровни выше заполнены) на глубине log(r - l) является 2^(log(r - l) - 1), Для одного узла мы берем O(logn) время.

Поэтому мы имеем общее время = O (logn * (2 ^ (log (r - l) - 1))).

Источник

Это может помочь:

T(#terms) = 2T(#terms/2) + a
T(2) = 2logn + b

Где a и b являются константами, а #terms относятся к числу терминов в полиноме. Это рекуррентное соотношение может быть решено с помощью теоремы Мастера или с помощью метода дерева рекурсии.

Источник
Другие вопросы по тегам