complexity-theory - 指标函数的重现

Question

假设您有一个递归函数，其中：

我知道第一个 if 语句的递归关系是 O(n)，而 else 条件的递归关系是 O(logn)。然而，我对计算整个函数的复杂性感到困惑。由于 n 支配 log(n)，所以整体复杂度是否只是 O(n)？

Answer 1

根据定义，大 O 是上限，所以它是 O(n)（因为 O(n) 大于 O(lg(n)）。阅读一些关于大 O 和大 theta Big-oh vs big- θ

编辑：

假设代码看起来像：

foo(x,y)
{
 if(y<0):
  //call some other function, or throw an error, otherwise we're stuck in an infinite loop
 else if(y==0):
   return 1
 else if(y%2!=0):
   return x*foo(x,y-1)
 else:
   return foo(x,y/2)*foo(x,y/2)
}

在这里，大 O 是 O(n)，但从技术上讲，它也是 O(n^2)、O(n^3) 等。这是因为大 O 是一个上限。

Big Theta（紧界）是 Theta(n)。

请注意，仅仅因为您可以通过除以 y/2 来减少 y，您不会减少对 foo 的调用，因为您执行的次数是原来的两倍：foo*foo。由于您将函数调用加倍，因此您不会获得 Theta(lg(n)) 的性能。

Answer 2

我相信您可以将其分解为 O(n) 是最坏的情况，而 O(logn) 是最好的情况。

只是给出一些想法，这绝不是一个完整的答案。