Анализ сложной простой рекурсивной функции

Question

Мне нужна помощь, чтобы понять анализ рекурсивных алгоритмов. Я быстро сделал этот алгоритм, и хотел бы знать, что сложность:

int FunctionExampple(A1, A2, ... An) 
{ 
    product = 1; 
    if(n == 2) 
    { 
     product = multi(A1, A2); 
    } 
    else 
    { 
     product = multi(A1, FunctionExample(A2, A3, ..., An)); 
    } 
    return product; 
} 

Теперь предполагая, что функция мульти занимает O времени (п^1,59), что бы сложность? Остается ли это O (n^1.59) или будут ли рекурсивные вызовы сделать O (n^1.59 * n) для учета количества рекурсивных вызовов? Спасибо, парни.

PS: Я просто написал это быстро, а синтаксис и все это не имеет значения.

Answer 1

Параметр 'n' in O (n ^1.59) измеряет размеры аргументов до 'multi', а не количество аргументов. Итак, что важно, так это то, как размер вывода из «multi» относится к размерам его входных данных. Например. если результат из «multi» в два раза превышает размер любого из его аргументов, тогда вызов multi (A, multi (B, C)), где A, B, C имеют размер n, равен O (n ^1,59 + (2n) ^1.59), и если вы затем перепутаете несколько вызовов на мульти, таким образом, вы получите экспоненциальный рост. С другой стороны, если «multi» возвращает значения, которые имеют тот же размер, что и его входы, тогда вы получаете O (k n ^1,59), где k - количество аргументов FunctionExample, а n - их наибольший размер.

Так что это зависит от того, как ведет себя «multi». Например. было бы огромной разницей, если бы это было умножение против умножения в конечном поле, так как для последнего результат не увеличивался бы от входных данных, тогда как для неограниченных целых чисел результат возрастает по размеру.