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））（不管其內容如何）