algorithm - 计算递归算法的复杂度

Question

func3(int n) {
    for (int i = 1; i<n; i++)
        System.out.println("*");
    if (n <= 1)
    {
        System.out.println("*");
        return;
    }
    if(n % 2 != 0) //check if odd
        func3(n - 1)
    func3(n / 2);
    return;
}

我需要计算这个算法的复杂度，当我的代码中有 for 和 2 次调用 func3 时，我该怎么做？

Answer 1

n 的位模式对说明这个问题很有帮助。

---

n 除以 2 相当于右移位模式一位，丢弃最低有效位 (LSB)。例如:

                          binary
                       ----------------------
n = 15                 |  0000 1111 
n / 2 = 7 (round down) |  0000 0111 (1) <- discard

• 奇数的 LSB 总是 1。
• 2 的幂仅设置了 1 位。

---

因此:

• 最好的情况是 n 是 2 的幂，即 func3(n - 1) 只被调用一次 在 n = 1 时结束。在这种情况下，时间复杂度是:

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

• 当 func3(n - 1) 在每次调用 func3 时总是调用一次时，最坏的情况是什么？ n/2 的结果必须始终为奇数，因此:

  n 的所有有效位都必须为 1。

  这对应于 n 等于二次方减一，例如3, 7, 15, 31, 63, ...

  在这种情况下，对 func3(n - 1) 的调用将不会产生对同一函数的另一个调用，因为如果 n是奇数则 n - 1 必须是偶数。此外，n/2 = (n - 1)/2(用于整数除法)。因此递推关系为:

  T(n) = 2 * T(n/2) + O(n) = O(n log n)
  

可以通过主定理获得这些结果。