细胞分裂

题目描述

1 个细胞的生命周期是 3 小时，1 小时分裂一次。求 n 小时后，容器内有多少细胞？请你用已经学过的递归时间复杂度的分析方法，分析一下这个递归问题的时间复杂度。

题目分析

以剩余时间为 4 为例：初始情况，只有一个细胞，还未分裂。第一行中第2列到第4列的数字表示对应周期细胞的数量，剩余时间为3时，生命周期为3的有一个细胞，生命周期为2的有一个细胞。

其实根据表格可以看出来，存活细胞总数 = 生命为（1，2，3）的细胞数量的总和，答案只跟这三个变量有关，可以用一个数组来存储它们。

代码实现

func cell(n int) int {
    // 初始情况, 只有一个生命为3的细胞
    // 存放不同生命值的细胞数量，生命值-1 ==> 细胞数量
    cells := [3]int{2: 1}
    // 细胞总数，当前存活细胞总数
    // totalNum, surviveNum := 1, 1
    // 当前存活细胞总数
    surviveNum := 1
    for ; n > 0; n-- {
        // 存活的细胞生命减1
        for i := 1; i < 3; i++ {
            cells[i-1] = cells[i]
        }
        // 存活的细胞都会分化出一个新的细胞
        // totalNum += surviveNum
        // 分化出的新细胞全为 生命为3
        cells[2] = surviveNum
        // 更新当前存活的细胞总数
        surviveNum = cells[0] + cells[1] + surviveNum
    }

    return surviveNum
}

时间复杂度

表面上是循环嵌套，时间复杂度为 O(n^2)，实际上内层循环次数并不随数据规模 n 的增大而增大，所以依旧是常数级的。其时间复杂度应该为 O(n)。