recursion - 递归函数的算法复杂度

Question

这是我的功能。这是一个简单的答案，我只是对答案没有信心。

  int calcul( int n) {
    if(n=1)
      return 1;
    else
      return calcul(n/2) + 1;
  }

现在，为了获得复杂性，我这样做：

T(n) = T(n/2) + O(1)

T(n/2) = T(n/4) + O(1)

...

T(1) = O(1)

现在，添加方程，我得到

T(n) = O(1) + O(1)...

那么最终答案是什么？

Answer 1

每次可以除以 （即次）时，您将执行一次n该2函数log n。

所以你得到O(log n).

编辑：

一个数的（以 2 为底的）对数是得到n的幂。2n

也就是说，2^(log n) = n，其中^表示取幂。

现在，计算 的近似值的一种简单方法log n是除以while 。n2n > 1

如果你划分了k时间，你会得到n < 2^k.

由于k - 1部门仍然产生n > 1，你也有n >= 2^(k-1)。

对 的每个成员取对数2^(k - 1) <= n < 2^k，得到k - 1 <= log n < k.

Answer 2

该算法与http://en.wikipedia.org/wiki/Binary_search_algorithm非常相似

所以，你可以阅读详细的解释为什么它O(log(n))

Answer 3

问题是每次您的输入除以 2 直到满足条件。前任。n/2, n/4, n/8....n/n

假设您的输入为 8，那么这个 log 8 base 2 将是 3。所以 O(logn)。常数不应计入。

希望能帮助到你。

Answer 4

我建议熟悉 Master 定理。在这种情况下，a=1，b=2 和 f=O(1)。由于对于 k = 0，f = Theta(1) = Theta(n^(log_2(1) log^kn) = Theta(log^kn)，因此我们处于定理的第二种情况并且 T(n) = Theta(log^(k+1) n) = Theta(log n)。

非常方便的定理，在与其他算法进行比较和进行其他类型的分析并不那么容易的情况下很有用。