c - if else 递归最差时间复杂度

Question

我很难找出下面代码的最差时间复杂度。
(这不是作业，请参阅 https://leetcode.com/problems/integer-replacement/description/。)

int recursion (int n) {
    if (n == 1)
        return 0;
    if (n % 2 == 0) {
        return recursion(n/2) + 1
    } else {
        return min(recursion(n / 2 + 1) + 1, recursion(n - 1)) + 1;
   }
}

我唯一知道的是当 N == 2 ^ k(k > 0) 时，最差的时间复杂度是 O(logN)。但是，我不清楚什么时候 N 不是 2^k。因为偶数 number/2 仍然可以得到奇数。有人说还是O(LogN)，我不信。

我知道代码不是最好的解决方案，只是想分析一下时间复杂度。我尝试了递归树和聚合分析，似乎没有帮助。

Answer 1

如果 n 是偶数，我们知道 T(n) = T(n/2) + 1，如果 n 是奇怪的是我们知道T(n) = T(n/2 + 1) + T(n-1) + 1。在后一种情况下，由于 n 是奇数，我们知道 n-1 必须是偶数。如果 n/2 + 1 是偶数 T(n) = T(n/4) + T(n/2) + 3 并且如果 n/2 + 1 是奇数 T(n) = 2*T(n/4) + T(n/2) + 3。

从上面的讨论，在最坏的情况下T(n)是基于T(n/2)和T(n/4 ) 在一般情况下。来自 Akra-Bazzi Theorem我们可以说，T(n) = O(n^((log(1+sqrt(5))-log(2))/log(2))) ~ O(n^0.69)(来自第一种情况)和 T(n) = O(n) 来自第二种情况(n/2 + 1 是奇数)。

然而，对于更严格的复杂性，我们应该在分析中进行更多的审查。