递归帕斯卡的三角行大O成本

Question

我正在攻读CS面试,我决定尝试解决自己的问题并递归解决.

我想要解决的问题是:我希望能够编写一个递归函数来找到pascal三角形的第n行.

Ex pascals(1) -> 1
   pascals(2) -> 1,1
   pascals(3) -> 1,2,1

我相信我已经解决了这个功能.它需要一个帮助函数才能从基础案例开始.

function int[] nthPascal(int[] a, int n){
  // in the case that the row has been reached return the completed array
  if(n==1){
    return a;
  }
  // each new row of pascal's triangle is 1 element larger. Ex 1, 11, 121,1331 etc. 
  int[] newA = new int[a.length()+1];

  //set the ends. Technically this will always be 1.
  // I thought it looked cleaner to do it this way. 
  newA[0]=a[0];

  newA[newA.length-1]=a[a.length-1];

  //so I loop through the new array and add the elements to find the value.
  //ex 1,1 -> -,2,- The ends of the array are already filled above
  for(int i=1; i<a.length; i++){

    // ex 1+1 = 2 for 1,1 -> 1,2,1
    newA[i]=a[i-1]+a[i]
  }
  //call the recursive function if we are not at the desired level
  return nthPascal(newA,n-1);
}

/**
*The helper function
*/
public int[] helperPascal(int n){
  return nthPascal(int[] {1},n);
}

我的问题是如何找到bigO成本？

我熟悉常见的算法成本以及如何找到它们.这种递归使我感到困惑.

我知道它显然不是常数,n,nlogn等.我的想法是它是3 ^ n？

我搜索了一个例子,发现: Pascal的Triangle Row Sequence 和 这个算法的运行时间是什么？(递归Pascal的三角形).但他们正试图在我认为的特定位置找到一个特定的元素.我找不到任何人用这种方式实现pascal的三角形并谈论bigO成本.

这是因为有一种更好的方法来编写递归行查找pascal的函数吗？如果是这样请分享:)

Answer 1

对于每个递归调用,您正在执行for循环的大小k,其中k是递归调用的深度(在深度k,您有一个大小的数组k).

要获得深度的完整行n,请调用nthPascal深度1,2,...,n.

因此,您的总体复杂性将是1+2+...+n=n(n+1)/2 = O(n²).

Answer 2

每次调用时nthPascal,它只会递归调用一次.因此,您可以通过添加函数的每次调用的时间复杂性来获得时间复杂度(不包括递归调用).(如果你有一个遍历二叉树的函数,它通常会递归调用两次,这会使计算变得更复杂.但是,由于它只调用一次,因此计算非常简单.)

每次调用函数都有一个执行a.length时间的循环,循环体在恒定时间内执行.除了分配数组之外,没有任何其他循环或任何其他语句在除了常量时间之外的任何时间执行,intA因为Java将初始化数组的每个元素.但结果是,当您nthPascal使用长度为M的数组调用时,执行时间将为O(M),不计算递归调用.

因此,假设对于某个常数k,执行时间大致为M*k,这意味着总执行时间将是1*k + 2*k + 3*k + ... +(n-1)*k.并且1 + 2 + 3 + ... + n-1是(n*(n-1))/ 2,其是O(n ²).所以O(n ²)就是您正在寻找的答案.