Java递归效率分析

Question

我需要帮助为下面的方法创建效率分析。我需要拿出：

1. 因素影响运行时
2. 什么是被计算（比较，操作）？
3. 最佳/最差情况
4. 大O符号

这是我到目前为止有：

1. 数组长度
2. 数学运算
3. 最坏情况和最好的情况是相同的，因为该方法将运行整个阵列，而不管其内容如何
4. 不知道

让我知道您的想法。

感谢

double sum(double[] array) { 
    return recursiveSum(array, 0, array.length - 1); 
} 

double recursiveSum(double[] array, int lo, int hi) { 
    if (lo == hi) { 
     return array[lo]; 
    } 

    int mid = (lo + hi)/2; 
    double leftsum = recursiveSum(array, lo, mid); 
    double rightsum = recursiveSum(array, mid+1, hi); 
    return leftsum + rightsum; 
} 

Answer 1

我的回答：

1. 数组长度
2. 不知道
3. 最坏情况和最好的情况是一样的，因为该方法将运行 全阵列（n（n））= 2 * f（n/2） - > f（n）= O（nlogn））（不管其内容如何）