确定递归函数的复杂性(Big O表示法)

Question

我明天有一个计算机科学中期,我需要帮助确定这些递归函数的复杂性.我知道如何解决简单的案例,但我仍然在努力学习如何解决这些更难的案例.这些只是我无法弄清楚的一些示例问题.任何帮助将非常感谢,并将大大有助于我的学习,谢谢!

int recursiveFun1(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun1(n-1);
}

int recursiveFun2(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun2(n-5);
}

int recursiveFun3(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun3(n/5);
}

void recursiveFun4(int n, int m, int o)
{
    if (n <= 0)
    {
        printf("%d, %d\n",m, o);
    }
    else
    {
        recursiveFun4(n-1, m+1, o);
        recursiveFun4(n-1, m, o+1);
    }
}

int recursiveFun5(int n)
{
    for (i = 0; i < n; i += 2) {
        // do something
    }

    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun5(n-5);
}

Answer 1

每个函数的Big O表示法的时间复杂度按数字顺序排列:

1. 第一个函数在到达基本情况之前被递归调用n次,因此O(n)通常称为线性函数.
2. 第二个函数每次都被称为n-5,所以我们在调用函数之前从n中减去5,但是n-5也是O(n).(实际上称为n/5次的顺序.并且,O(n/5)= O(n)).
3. 这个函数是log(n)base 5,因为我们在调用函数之前每次除以5,所以它O(log(n))(基数5),通常称为对数,最常见的是Big O表示法和复杂性分析使用base 2.
4. 在第四个中,它是O(2^n)或指数,因为每个函数调用自己调用两次,除非它已被递归n次.

5. 对于最后一个函数,for循环取n/2,因为我们增加2,递归取n-5,因为for循环是递归调用的,因此时间复杂度在(n-5)*(n/2)=(2n-10)*n = 2n ^ 2 - 10n,由于渐近行为和最坏情况情景考虑或大O正在努力的上限,我们只关心最大项O(n^2).

   祝你的中期好运;)

Answer 2

对于的情况n <= 0,T(n) = O(1).因此,时间复杂度将取决于何时n >= 0.

我们将n >= 0在下面的部分中考虑这个案例.

1.

T(n) = a + T(n - 1)

其中a是常数.

通过归纳:

T(n) = n * a + T(0) = n * a + b = O(n)

其中a,b是常数.

2.

T(n) = a + T(n - 5)

其中a是常数

通过归纳:

T(n) = ceil(n / 5) * a + T(k) = ceil(n / 5) * a + b = O(n)

其中a,b是常数,k <= 0

3.

T(n) = a + T(n / 5)

其中a是常数

通过归纳:

T(n) = a * log5(n) + T(0) = a * log5(n) + b = O(log n)

其中a,b是常数

4.

T(n) = a + 2 * T(n - 1)

其中a是常数

通过归纳:

T(n) = a + 2a + 4a + ... + 2^n * a + T(0) * 2 ^ n 
     = a * 2^(n+1) - a + b * 2 ^ n
     = (2 * a + b) * 2 ^ n - a
     = O(2 ^ n)

其中a,b是常数.

5.

T(n) = n / 2 + T(n - 5)

我们可以通过归纳证明T(5k) >= T(5k - d)d = 0,1,2,3,4

写n = 5m - b(m,b是整数; b = 0,1,2,3,4),然后m = (n + b) / 5:

T(n) = T(5m - b) <= T(5m)

(实际上,为了更严格,这里T'(n)应该定义一个新的函数,以便T'(5r - q) = T(5r)在哪里q = 0, 1, 2, 3, 4.我们知道T(n) <= T'(n)如上所述.当我们知道它T'(n)在O(f),这意味着存在常数a,b因此T'(n) <= a * f(n) + b,我们可以得出它T(n) <= a * f(n) + b,因此T(n)是在O(f)这一步是不是真的有必要,但它更容易认为当你没有对付其余部分.)

扩大T(5m):

T(5m) = 5m / 2 + T(5m - 5) 
      = (5m / 2 + 5 / 2) * m / 2 + T(0) 
      = O(m ^ 2) = O(n ^ 2)

因此,T(n)是O(n ^ 2).

Answer 3

我发现用于近似递归算法复杂度的最佳方法之一是绘制递归树.一旦你有了递归树:

Complexity = length of tree from root node to leaf node * number of leaf nodes

1. 第一个函数将具有n叶节点的长度和数量,1因此复杂性将是n*1 = n

2. 第二个函数将n/5再次具有叶节点的长度和数量,1因此复杂性将是如此n/5 * 1 = n/5.它应该近似于n

3. 对于第三个函数,因为n在每次递归调用时除以5,递归树的长度将是log(n)(base 5),并且叶节点的数量将再次为1,因此复杂性将是log(n)(base 5) * 1 = log(n)(base 5)

4. 对于第四个函数,因为每个节点将具有两个子节点,叶节点的数量将等于,(2^n)并且递归树的长度将是n如此复杂度(2^n) * n.但由于n在前面是微不足道的(2^n),它可以被忽略,复杂性只能说是复杂的(2^n).

5. 对于第五个函数,有两个元素引入复杂性.复杂性由函数的递归性质和for每个函数中的循环引入的复杂性引入.进行上述计算时,~ n由于for循环,函数的递归性质引入的复杂性将是复杂性n.总的复杂性将是n*n.

注意:这是计算复杂性的快速而肮脏的方法(没有官方!).很想听听有关这方面的反馈.谢谢.

Answer 4

我们可以用数学方法证明它，这是我在上述答案中遗漏的东西。

它可以极大地帮助您了解如何计算任何方法。我建议从上到下阅读它以完全理解如何做到这一点：

1. T(n) = T(n-1) + 1这意味着方法完成所需的时间等于相同的方法，但 n-1 这是T(n-1)我们现在添加的，+ 1因为它是完成一般操作所需的时间（除了T(n-1)）。现在，我们会发现T(n-1)如下：T(n-1) = T(n-1-1) + 1。看起来我们现在可以形成一个可以给我们某种重复的函数，这样我们就可以完全理解了。我们将把右侧的T(n-1) = ...而不是T(n-1)在方法里面，T(n) = ...这会给我们：T(n) = T(n-1-1) + 1 + 1这是T(n) = T(n-2) + 2或者换句话说，我们需要找到我们丢失的k: T(n) = T(n-k) + k。下一步是采取n-k并声明，n-k = 1因为在递归结束时，当n<=0. 从这个简单的等式我们现在知道k = n - 1。让我们放置k在我们的最终方法中：T(n) = T(n-k) + kwhich 将给我们：T(n) = 1 + n - 1which is just nor O(n)。
2. 与 1 相同。你可以自己测试一下，看看你得到O(n).
3. T(n) = T(n/5) + 1和以前一样，此方法完成的时间等于相同方法的时间，但这n/5就是它被限制为 的原因T(n/5)。让我们T(n/5)在 1 中找到：T(n/5) = T(n/5/5) + 1这是T(n/5) = T(n/5^2) + 1. 让我们将其放置T(n/5)在内部T(n)进行最终计算：T(n) = T(n/5^k) + k。再次和以前一样，n/5^k = 1这n = 5^k正是问什么是 5 的幂，会给我们 n，答案是log5n = k（以 5 为底的对数）。让我们把我们的调查结果T(n) = T(n/5^k) + k如下：T(n) = 1 + logn这是O(logn)
4. T(n) = 2T(n-1) + 1我们这里的内容与之前基本相同，但这次我们递归调用该方法 2 次，因此我们将其乘以 2。让我们找出T(n-1) = 2T(n-1-1) + 1哪个是T(n-1) = 2T(n-2) + 1. 我们的下一个地方和以前一样，让我们​​把我们的发现：T(n) = 2(2T(n-2)) + 1 + 1这T(n) = 2^2T(n-2) + 2给了我们T(n) = 2^kT(n-k) + k。让我们k通过声明n-k = 1which is 来找到k = n - 1。让我们放置k如下：T(n) = 2^(n-1) + n - 1大致是O(2^n)
5. T(n) = T(n-5) + n + 1它几乎与 4 相同，但现在我们添加，n因为我们有一个for循环。让我们找出T(n-5) = T(n-5-5) + n + 1哪个是T(n-5) = T(n - 2*5) + n + 1。让我们把它放在: T(n) = T(n-2*5) + n + n + 1 + 1)which isT(n) = T(n-2*5) + 2n + 2)和 for the k: T(n) = T(n-k*5) + kn + k)again: n-5k = 1which is n = 5k + 1that is about n = k. 这将给我们：T(n) = T(0) + n^2 + n大致是O(n^2).

我现在建议阅读其余的答案，现在会给你一个更好的视角。祝你好运赢得那些大 O :)

Answer 5

这里的关键是可视化调用树。一旦完成，复杂性是：

nodes of the call tree * complexity of other code in the function

后一项的计算方式与我们对普通迭代函数的计算方式相同。

相反，完整树的总节点计算为

                  C^L - 1
                  -------  , when C>1
               /   C - 1
              /
 # of nodes =
              \    
               \ 
                  L        , when C=1

其中 C 是每个节点的子节点数，L 是树的级别数（包括根）。

很容易想象这棵树。从第一次调用（根节点）开始，然后绘制与函数中递归调用次数相同的子代数。将传递给子调用的参数写为“节点的值”也很有用。

所以，在上面的例子中：

1. 这里的调用树是 C = 1, L = n+1。其余函数的复杂度为 O(1)。因此总复杂度为 L * O(1) = (n+1) * O(1) = O(n)

n     level 1
n-1   level 2
n-2   level 3
n-3   level 4
... ~ n levels -> L = n

2. 这里的调用树是 C = 1，L = n/5。其余函数的复杂度为 O(1)。因此总复杂度为 L * O(1) = (n/5) * O(1) = O(n)

n
n-5
n-10
n-15
... ~ n/5 levels -> L = n/5

3. 这里的调用树是 C = 1，L = log(n)。其余函数的复杂度为 O(1)。因此总复杂度为 L * O(1) = log5(n) * O(1) = O(log(n))

n
n/5
n/5^2
n/5^3
... ~ log5(n) levels -> L = log5(n)

4. 这里的调用树是 C = 2，L = n。其余函数的复杂度为 O(1)。这次我们使用调用树中节点数的完整公式，因为 C > 1。因此总复杂度为 (C^L-1)/(C-1) * O(1) = (2^n - 1 ) * O(1) = O(2^n)。

               n                   level 1
      n-1             n-1          level 2
  n-2     n-2     n-2     n-2      ...
n-3 n-3 n-3 n-3 n-3 n-3 n-3 n-3    ...     
              ...                ~ n levels -> L = n

5. 这里的调用树是 C = 1，L = n/5。其余函数的复杂度为 O(n)。因此总复杂度为 L * O(1) = (n/5) * O(n) = O(n^2)

n
n-5
n-10
n-15
... ~ n/5 levels -> L = n/5