函数的运行时间复杂度

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在每次递归调用时都会减半。每个调用也只进行持续的工作。这是重要的概念。

在大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))。