【数据结构与算法】递归树

亦凉 2022-11-29 13:16 202阅读 0赞

1.树、二叉树  
2.二叉查找树  
3.平衡二叉树、红黑树  
**4.递归树**

### 一、什么是递归树 ###

如果我们把这个一层一层的分解过程画成图，它其实就是一棵树。我们给这棵树起一个名字，叫作递归树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]  
时间复杂度分析的递归树法

1.  分析每一步核心操作的时间复杂度
2.  分析树高：最大树高和最小树高
3.  计算每层复杂度，全加起来（放缩法调整）

### 二、实战 ###

**实战1:快速排序**  
快速排序在最好情况下，每次分区都能一分为二，这个时候用递推公式 T(n)=2T(2n)+n，很容易就能推导出时间复杂度是 O(nlogn)。

1.  分割算法是O(n)  
    2,树高最大最小都是 logn，所以O(logn)  
    **实战2：斐波那契数列:**
2.  加和算法1
3.  节点数为倍增。 通项为2^h
4.  h高度最高n，最低n/2.相当于求等比数列前n项和。时间复杂度就介于 O(2n) 和 O(2n/2) 之间  
    **实战3:全排列**

// 调用方式：
    // int[]a = a={1, 2, 3, 4}; printPermutations(a, 4, 4);
    // k表示要处理的子数组的数据个数
    public void printPermutations(int[] data, int n, int k) { 
      if (k == 1) { 
        for (int i = 0; i < n; ++i) { 
          System.out.print(data[i] + " ");
        }
        System.out.println();
      }
    
      for (int i = 0; i < k; ++i) { 
        int tmp = data[i];
        data[i] = data[k-1];
        data[k-1] = tmp;
    
        printPermutations(data, n, k - 1);
    
        tmp = data[i];
        data[i] = data[k-1];
        data[k-1] = tmp;
      }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][20200821170243143.png_pic_center]

### N、问题 ###

**1 个细胞的生命周期是 3 小时，1 小时分裂一次。求 n 小时后，容器内有多少细胞？请你用已经学过的递归时间复杂度的分析方法，分析一下这个递归问题的时间复杂度。**  
F(n)=F(n-1) \* 2 - F(n-4)  
一次乘法和一次减法一起看作一次基本操作消耗，那么情况和斐波那契数列很像。  
最高的树应该有n层， 最短的是n/4层，每层操作数都是指数增长。  
那么时间复杂度应该是在O(2^n)量级的。

最开始为0的时刻，放入了1个细胞，然后1小时的时候，分裂变为了2个细胞，然后2小时的时候，分裂成了4个细胞，然后3小时的时候，分裂成了8个细胞，但是最早的那1个细胞死掉了，所以最终剩下7个细胞。列举时刻与个数的关系:

时刻: 0 1 2 3  
个数: 1 2 4 7

将细胞分裂分为两个步骤，先分裂，后死亡。比如第四个小时的时候，从3小时的7个细胞分裂成14个，然后计算要死亡细胞的个数，直观上我们会认为，第1小时的时候2个细胞现在应该会死亡了，所以4小时的时候，细胞个数应该是7\*2 - 2 = 12个，得到4小时之后的公式f(n) = f(n-1) \* 2 - f(n-3)。

但这是错误的，因为第1小时的2个细胞，其中一个已经在第3小时的时候死掉了，因此第4小时的时候只会死掉1个细胞，正确的个数应该是 14 - 1 = 13.

经过这样分析，死掉的细胞数并不是前3小时的细胞总数f(n-3)，因为这里面包含n-3时刻新生的细胞和老细胞，很显然老细胞在n时刻之前就已经死完了。此时死掉的细胞数应该是n-3时刻新生的细胞数，而n-3时刻新生的细胞数正是前一时刻老细胞分裂而来的即f(n-4)，因此正确的计算公式是 f(n) = f(n-1) \* 2 - f(n-4)。

用递归代码写出来就是

int F(int n){ 
        If(n<0) return 0;
        If(n==0) return 1;
        If(n==1) return 2;
        If(n==2) return 4;
        If(n==3) return 7;
        return F(n-1) * 2 - F(n-4);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/bfe17f4ce55a40428b7fa78ae438063e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/e830a73fd27c46dbb1f7b9e0f9c154a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/017917084193466c8b74d16e6924ab8e.png
[20200821170243143.png_pic_center]: /images/20221124/8a430bca781448219128f5e3fbdc826f.png