有些同学不明白点赞第一的意思，在此试着解释一下。

假设细胞先分裂再死亡，即，每个细胞分裂三次后死亡（存活三个小时）。

n 从第 0 个小时开始，

n = 0，f(0) = 1

n = 1，f(1) = 2*f(1)

n = 2，f(2) = 2*f(1)

n = 3，f(3) = 2*f(2) - f(0) ，减去存活了三个小时的细胞个数。

n = 4，f(4) = 2*f(3) - f(1)，减去存活了三个小时的细胞个数。

以此类推：

f(n) = 2*f(n-1) - f(n-3)，减去存活了三个小时的细胞个数。

点赞第一的递推可能有些问题，这里假设经过三个小时的细胞分裂后再死亡。
通过留言可以看出有些同学可能没搞明白细胞分裂的方式，根据题意，细胞的生命周期是三个小时，一个小时后，第一个细胞分裂，此时细胞总数变成 2，但是这两个细胞的生存时间是不一样的，如果都当成新生细胞即存活时间为 0，那么给定的 3小时生命周期也就没意义了，所以这个时候其中一个细胞的生存时间变成了 1，另外一个刚分裂出来的是 0，下面简单表示一下分裂进程（-1 表示死亡）
时间 细胞状态 (生存时间) 细胞总数
  0 0 1
  1 1 0 2
  2 2 1 0 0 4
  3 -1 2 1 1 0 0 0 0 7
  4 -1 2 2 1 1 1 1 0 0 0 0 0 0 0 13
  5 -1 -1 2 2 2 2 1 1 1 1 1 1 1
                   0 0 0 0 0 0 0 0 0 0 0 0 0 24
  .... ............................................. ....
f0 = 1
f1 = 2
f2 = 4
f3 = 7
可以发现到第四个小时的时候，规律出来了，在第四个小时死亡的细胞是三小时前也就是第一个小时的时候同时出生的细胞，而在第一个小时同时出生的细胞数等于第一个小时前一个小时的细胞总数
所以有递推式：f(n) = 2 * f(n - 1) - f(n - 4)

思考题：
f0=1
f1=1+1=2
f2=1+1+2=4
f3=1+1+2+3-1=6 = f1 + f2
f4=1+1+2+3-1+5-1=10 = f2+f3
f5=1+1+2+4-1+5-1+8-2=16 = f3+f4
f（n）= f（n-1） + f（n-2）

与斐波那契数列的递归复杂度相同。

如果到了第三小时先分裂再死亡应该是f(n) = 2*f(n-1) - f(n-4)

—————————-
 
 public static int func(int hour){
   if(hour == 0) return 1;
   if(hour == 1) return 2;
   if(hour == 2) return 4;
   if(hour == 3) return 7;
   return 2*func(hour -1) - func(hour - 4);
 }

————-
带入hour=4
结果： 2 * func(3)-func(0)= 13

如果第三个小时不分裂，死亡：
f(n)=f(n-1)+f(n-2)
第三个小时分裂之后再死亡：
有两个公式表达
f(n)=f(n-1)+f(n-2)+f(n-3)

之后再用斐波那契数列中老师的树的分析方式分析，得到结果
第三个小时不分裂，就死亡，与斐波那契数列结果相同
第三个小时先分裂再死亡，时间复杂度在
O(3^n/3）至O(3^n)之间

假设细胞3小时候先分裂再死亡。
life3 表示还能活3个小时， life2表示还能活2个小时，life1表示还能活1个小时
假设在第x时刻，存活细胞数为life1 = x, life2= y, life3 = z个，总细胞sum(x)
在第x + 1时刻，此时刻的life1细胞均来自上一时刻的life2细胞。此时刻life2细胞均来自上一时刻的life3细胞。上一时刻life1细胞死亡后，会分列均等数量life3细胞，因此上一时刻所有细胞均会分裂，所以此时刻life3细胞等于上一时刻所有细胞数。
所以x + 1时刻，life1 = y, life2 = z, life3 = sum(x), sum(x+1) = y + z + sum(x)
x + 2, life1 = z, life2 = sum(x), life3 = sum(x + 1), sum(x+2) = z + sum(x) + sum(x + 1)
x + 3, life1 = sum(x), life2 = sum(x + 1), life3 = sum(x + 2) , sum(x + 3) = sum(x) + sum(x + 1) + sum(x + 2)
因此递推式为
sum(x) = sum(x - 1) + sum(x - 2) + sum(x - 3)
1 sum函数
3 sum函数
9 sum函数
所以是3的0次方+3的1次方+3的二次方，为几何级数，算法复杂度为O(3的n次方)

老师，有几个问题不明白：
1. 求归并排序的时间复杂度中
满二叉树的高度计算公式中的n指的是树中的节点的总个数，而归并排序中的n指的却是叶子节点的个数。所以归并排序中树的高度，我计算出来的是h=log2^2n-1。
2. 实战二中
“f(n) 分解为 f(n-1) 和 f(n-2)，每次数据规模都是 -1 或者 -2，叶子节点的数据规模是 1 或者 2。“
叶子节点为1或者2都不能再往下分叉了，所以，我计算出来的最长路径是n-2。举个具体的例子：n=5时，最长路径为3。
我计算出来的最短路径依据n的不同还会不同，
具体的例子：n=5时，最短路径为2，n=6时，最短路径依然为2。

是我理解的有偏差吗？请老师指点。

有几点问题不懂
1.实战二：分析斐波那契数列的时间复杂度 一节提到
“f(n) 分解为 f(n-1) 和 f(n-2)，每次数据规模都是 -1 或者 -2，叶子节点的数据规模是 1 或者 2。所以，从根节点走到叶子节点，每条路径是长短不一的。如果每次都是 -1，那最长路径大约就是 n；如果每次都是 -2，那最短路径大约就是 n/2。”数据规模都是-1，-2 这怎么理解？每次都是-1，最长路径大约就是n 这又是怎么理解的？
2.实战3中提到
“第一层分解有 n 次交换操作，第二层有 n 个节点，每个节点分解需要 n-1 次交换，所以第二层总的交换次数是 n*(n-1)。第三层有 n*(n-1) 个节点，每个节点分解需要 n-2 次交换，所以第三层总的交换次数是 n*(n-1)*(n-2)。”
交换操作的次数是怎么的出来的？
这对于我来讲就好比，数学老师讲了一堆看似简单的东西（有同学基础不好），最后老师最后落笔：所以1+1=2，但我还是一脸懵逼