包含递归函数的循环的时间复杂度

Question

我在处理以下代码的时间复杂度时遇到了困难：

int f(int n)  {
int x=1;
for (int k=0; k<n; k++){
x *=n*n
} 
g(n);
return x; }

其中 g(n( 是一个递归函数：

void g(int n){
if (n<1)
return;
g(n/2);
}

谢谢！

Answer 1

int f(int n)  {
int x=1;
// O(n) time complexity due to for loop
for (int k=0; k < n; k++) { 
// O(1) 
x *= n*n 
} 
// O(log n)(base 2) because for every time we divide by 2 before calling the function 
g(n); 
return x;
}
void g(int n){
if (n<1)
return;
g(n/2);
}

现在 O(logn( 比 O(n( 快，这意味着代码的整体时间复杂度很简单！！

Answer 2

g(n)的复杂性O(log n).

f(n)的复杂性是O(n + log n)(n用于for循环，log n用于调用g(n)(——或者简单地O(n)正如希普拉·古普塔所指出的那样。

int f(int n)  {
int x=1;
for (int k=0; k < n; k++) { // O(n)
x *= n*n // O(1)
} 
g(n); // O(log n)
return x;
}

O(n * 1 + log(n) + 1)

也就是说，如果我们忽略g(n)永远不会达到n<1条件的事实，如果n >= 1(堆栈溢出！说到这里 - 欢迎来到网站！：-P