函数的运行时间复杂度

Question

我需要找到这个递归函数的运行时间复杂度

int f3(int i, int j) {
  if(i<10) {
  return i;}
else if(i<100) {
  return f3(i-2,j);}
else {return f3(i/2, j);}
}

是 O(logn) 还是 O(n)？根据我的理解，因为它将数字除以二，所以具有较高 n 的呼叫数量的增长率不是线性的，而是对数的。但运行时间还取决于 n 有多大，所以我不确定正确答案是什么。

Answer 1

你是对的，对于较大的

i

值，

i

在每次递归调用时都会减半。每个调用也只进行持续的工作。这是重要的概念。

在big-O分析中，我们只关心函数的增长率。对于

i < 100

，该函数需要“线性”时间并不重要，因为在宏伟的计划中，这对于

i < 100

来说是恒定的工作量。

另一种理解这一点的方法是，我们可以用递归来表示该算法的运行时间。

对于

i >= 100

，

i

减半，并且该函数仅持续工作。对于

i < 100

，我们可以将其视为恒定的工作量。所以我们有：

T(i) = O(1)             if i < 100
T(i) = T(i/2) + O(1)    otherwise

这个问题的解决方案是

O(log(i))

。