Анализ затрат на программу Recursive Pascal Triangle - PullRequest
Новая
       69

Анализ затрат на программу Recursive Pascal Triangle

0 голосов
/ 06 августа 2020 
#include<iostream>
using namespace std;

int pascal(int row, int col) 
{
  if (col == 0 || col == row) 
  {
    return 1;
  } 
  else
  {
    return pascal(row - 1, col - 1) + pascal(row - 1, col);
  }
}


int main()
{
    system("cls");
    int row;
    cout<<"Enter n : ";
    cin>>row;

    
    for (int i=0;i<row;i++)
    {
        for(int col =0;col<=i;col++)
            cout<<pascal(i,col);

        cout<<"\n";
    }

    return 0;
}

Я понимаю анализ стоимости основной функции, но не могу понять анализ стоимости рекурсивной функции. Сколько раз выполняется рекурсивная часть pascal (i-1, j-1) + pascal (i-1, j)?

1 Ответ

0 голосов
/ 06 августа 2020

Во-первых, я не совсем уверен, что вы пытаетесь вычислить, но вы можете уделить больше внимания крайним случаям, например, отрицательным аргументам или случаям, когда row < col.

Теперь, без при условии col == row (и при условии col >= 0) общее количество вызовов будет суммой треугольника Паскаля, что примерно равно pow(2, col+1) - 1. Таким образом, это простая верхняя граница стоимости.

В точке, где col == row (предполагая изначально row > col), ваше дерево «усечено». Рассчитать сложность с этого момента - это интересный математический вопрос, выходящий за рамки Stack Overflow (хотя вы можете попробовать Math Stack Exchange ).

Обратите внимание, что этот код чрезвычайно неэффективно - экспоненциальное время работы в большинстве случаев непомерно дорого, и эту специфическую проблему c можно решить с помощью мемоизации со значительно меньшими затратами (менее pow(col, 2)).

...