Может ли кто-нибудь помочь понять рекуррентное отношение?

Я изучаю временную сложность и имею эту функцию:

public static double pow( double x, int n ) {
    if( n==0 ) return 1.0;
    return x*pow(x,n-1); 
}

Мне нужно найти рекуррентное соотношение для его временной сложности, и я знаю, что ответ T(n) = T(n-1) + O(1), чего я не понимаю, потому что Я думаю, что должно быть T(n) = T(n-1) + O(n). Мое рассуждение состоит в том, что я умножаю каждый рекурсивный вызов на x, который происходит n раз, так что это O (n), верно?

* редактировать: я думаю, что понимаю свою ошибку. T(n) = T(n-1) + O(1) предназначен только для этого конкретного вызова, так что это явно O(1), и решение повторения приводит к n*T(n-1) + (n-1)O (1) поэтому (n-1)O(1) игнорируется, поскольку оно меньше n*T(n-1). Таким образом, мы получаем порядок роста = O (n).


recurrence time-complexity
person odd choice    schedule 12.02.2014    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Вам не нужно учитывать каждое умножение. Рекуррентные отношения связаны с тем, как вызов одного номера связан с тем же вызовом другого номера. В этом случае для вычисления pow(x,n) требуется, чтобы вы уже знали pow(x,n-1) — это часть T(n) = T(n-1). Теперь, что вам дополнительно нужно сделать, чтобы рассчитать pow(x,n), учитывая, что у вас уже есть pow(x,n-1)? Это только одно умножение — x*pow(x,n-1) — равно O(1), поэтому общее рекуррентное отношение равно T(n) = T(n-1) + O(1). Все остальные умножения уже учтены в T(n-1)...

person twalberg    schedule 12.02.2014