Java 中递归算法的时间复杂度

Question

我刚从另一个post那里得到这个算法，但我想知道如何计算这个算法的temporal complexity？我是一名学生，不太了解如何去做。

 public static void getSum(int[] numbersArray, int starting, int sum)
 {
   if(numbersArray.length == starting)
   {
     // Now we print sum here
     System.out.println(sum);
     return;
   }

   int value = sum + numbersArray[starting];

   getSum(numbersArray, starting + 1, value);
   getSum(numbersArray, starting + 1, sum);
 }

Answer 1

假设 numbersArray 的长度为 5。我假设有人会用 starting = 0 来调用它，即 getSum(numbersArray, 0, 0)。现在：

这将调用 getSum(numbersArray, 1, x) 两次。

getSum(numbersArray, 1, x)的每次调用都会调用getSum(numbersArray, 2, x)两次。

getSum(numbersArray, 2, x)的每次调用都会调用getSum(numbersArray, 3, x)两次。等等。

当我们到达getSum(numbersArray, 5, x)时，时间是恒定的；我们称它为 baseTime.

假设我们说T(n)是执行getSum(numbersArray, n, x)的时间。那么T(5)就是baseTime； T(4) = 2*T(5); T(3) = 2*T(4);等等。也就是说整个调用的时间，T(0) = 2*T(1) = 2*2*T(2) = 2*2*2*T(3) = 2*2*2*2* T(4) = 2*2*2*2*2*T(5) = 2*2*2*2*2*baseTime。这告诉您算法的时间与 2^m 成正比，其中 m 是数组的长度。所以答案会写成 O(2^m).

Java 中递归算法的时间复杂度

Temporal complexity of a recursive algorithm in Java

java

algorithm

complexity-theory

temporal