为什么这些函数具有不同的时间复杂度？

Question

我知道 mergeSort 函数需要 O(logn)，合并函数需要 O(n)，因此总复杂度为 O(nlogn)。

void mergeSort(int arr[], int l, int r){
    if(l >= r){
        return;
    }
    int m = (l + r) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m+1, r);
    merge(arr, l, m, r);  
}

现在假设我使用相同的逻辑来实现以下数组元素总和的代码

int arraySum(int arr[], int l, int r){
    if(l == r){
        return arr[l];
    }
    int mid = (l + r) / 2;
    int one = arraySum(arr[], l, mid);
    int two = arraySum(arr[], mid + 1, r);
    return one + two;
}

现在这个 arraySum() 函数与 mergeSort() 相同，除了 merge() 即。 O(n) 部分。所以，arraySum() 的时间复杂度不应该是 O(logn)。但我知道这是不可能的，因为有 n 个元素，每个元素的访问时间都是 O(1)，而且必须是 O(n)。现在我对这两种逻辑感到困惑。为什么 mergeSort() 需要 O(logn) [忽略 merge() 函数] 而这个 arraySum() 需要 O(n)，即使它们是相同的。

Answer 1

arraySum 的时间复杂度为 O(n)，而 mergeSort() 的时间复杂度为 O(n log(n))。请注意 | 的每个实例的每个实例return一+二； |复杂度为 O(1)，而 | 的每个实例合并（arr，l，m，r）； |复杂度为 O(r-l).

对于n个元素，arraySum会进行n-1次加法，而mergeSort会进行n⌈log2(n)⌉次移动

为什么这些函数具有不同的时间复杂度？

Why do these functions have different time complexities?

c

mergesort

time-complexity