if if递归最坏时间复杂度

我有一些麻烦弄清楚下面代码的最坏时间复杂度。
（这不是一门功课，看https://leetcode.com/problems/integer-replacement/description/。）if if递归最坏时间复杂度

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)，但我不相信。

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

来源

2017-11-11 nathan

你的其他情况有错误的说法，它应该是'（n + 1）/ 2' –

@BlackMamba。嗨，（n + 1）会溢出。但我有其他错误。 Updated.Thanks非常多 – nathan

我看到了leetcode问题陈述。我不知道在前两个版本中，最后一个分支（用'min'选择其中一个）与它有关 - 它不应该是“an'else”的一部分，如果“then”无论如何，''终止于无条件的'return'。 – greybeard

如果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是奇数）。

但是，对于更复杂的情况，我们应该在我们的分析中仔细检查。

来源

2017-11-11 18:44:30 OmG

嗨，阿克拉 - 巴齐引起了我的思想。我将这个应用于T（n）= T（n/4）+ T（n/2）。 – nathan

如果'n'是奇数，那么'n/2 + 1'可以是奇数或偶数 - 考虑n = 7和n = 9。 – algrid

@OmG，如果'n = 9'，则'n/2 + 1'等于'5'。 – algrid

if if递归最坏时间复杂度

回答

相关问题