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

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

g(n) 的复杂度是 O(log n)。

f(n) 的复杂度为 O(n + log n)（n 用于 for 循环，log n 用于调用 g(n)）--或如 Shipra Gupta 所指出的那样 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

Answer 2

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) 快，这意味着代码的整体时间复杂度简直就是 O(n)！！

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

Time Complexity of loop that contains recursive function

recursion

time

complexity-theory

loops