c - 包含另一个函数的递归函数复杂度（大 O 表示法）

Question

我见过很多类似的问题，但不是我想要的。我应该找到下面代码的复杂性。使这段代码与我在这里看到的不同的是，我必须找到复杂性的函数包含另一个具有给定复杂性的函数。

我想我可以解决这个问题，但不能给出正确的答案。任何详细的解释都会非常好，也可以帮助我更好地理解在这些函数中寻找复杂性的流程。代码在 C 中。

 void f(int v[], int n, int i, int j){
    int a = v[i]; 
    int b = v[j]; 
    int m = (i+j)/2;
    g(v,n);
    if(i<j){
        if(a<b) f(v,n,i,m);
        else f(v,n,m,j)
    }
    return; 
}

f 函数在 main 中调用，其中 v 是一个数组：f(v, n, 0, n-1)。g 函数复杂度为 O(n)。

现在，我真的无法在 O(log n) 或 O(n log n) 之间做出决定。看到我们使用 int m 将工作空间分成两半，我知道它是对数的，但是 G 函数是否加起来并将所有内容变成 O(n log n)？

谢谢你。

PS：如果已经问过这样的答案，我找不到它，并且重定向会很好，以防其他人偶然发现与我相同的问题。

标签： calgorithmsortingtime-complexitybig-o

Answer 1

您的f函数将准确执行log(n)时间（和之间的范围i总是j减半）；每一次，它都会执行g，额外的成本为O(n). 因此，总复杂度为，即调用O(n * log(n))内部循环*的总次数。g

（*出于解释的目的，我假设有一个内部循环g，因为这是您在许多但肯定不是全部O(n)功能中找到的）。