阿克苏网站开发,怎样做信息收费网站,网站用什么做关键词,设计签名免费名字1.树、二叉树 2.二叉查找树 3.平衡二叉树、红黑树 4.递归树
一、什么是递归树
如果我们把这个一层一层的分解过程画成图#xff0c;它其实就是一棵树。我们给这棵树起一个名字#xff0c;叫作递归树。 时间复杂度分析的递归树法
分析每一步核心操作的时间复杂度分析树高它其实就是一棵树。我们给这棵树起一个名字叫作递归树。 时间复杂度分析的递归树法
分析每一步核心操作的时间复杂度分析树高最大树高和最小树高计算每层复杂度全加起来放缩法调整
二、实战
实战1:快速排序 快速排序在最好情况下每次分区都能一分为二这个时候用递推公式 T(n)2T(2n)n很容易就能推导出时间复杂度是 O(nlogn)。
分割算法是O(n) 2,树高最大最小都是 logn所以O(logn) 实战2斐波那契数列:加和算法1节点数为倍增。 通项为2^hh高度最高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;}
}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(n0) return 0;If(n0) return 1;If(n1) return 2;If(n2) return 4;If(n3) return 7;return F(n-1) * 2 - F(n-4);
}
