包含另一个函数的递归函数复杂性（大 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; 
}

在main中调用了f函数，其中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：如果已经有人问过这样的答案，我找不到它，重定向会很好，以防其他人遇到与我相同的问题。

Answer 1

您的 f 函数将恰好执行 log(n) 次（i 和 j 之间的范围总是减半）；每一次，它都会执行 g，并增加 O(n) 的成本。因此，总复杂度为O(n * log(n))，也就是g的内循环*被调用的总次数

(* 出于解释目的，我假设 g 中有一个内部循环，因为这是您在许多但肯定不是全部 O(n) 函数中发现的。

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

Recursive functions complexity containing another function (Big O notation)

c

sorting

algorithm

big-o

time-complexity