无需执行拆分，计算数组拆分树生成的数组总数

首先，我们先明确divide函数的行为：它会将输入数组按指定size（下文记为m）拆分成长度不超过m的子数组（chunk），如果拆分后得到的子数组数量仍大于m，则会将这些子数组组成的新数组作为输入递归执行拆分，直到最终返回的数组长度≤m。整个过程会生成一棵以数组为节点的树，我们需要计算这棵树的所有节点总数（即函数创建的所有数组数量）。

核心推导思路 #

我们可以通过递归定义和迭代求和的方式来计算总数：

1. 定义关键序列 #

首先生成一个序列k₀, k₁, ..., k_d，其中：

• k₀ = ⌈n/m⌉：将初始长度为n的数组拆分成最大长度m的子数组，得到的子数组数量（向上取整，可用(n + m - 1) // m计算）
• k_{i+1} = ⌈k_i/m⌉：将第i层的子数组集合再拆分成最大长度m的数组，得到的新数组数量
• 终止条件：当k_d ≤ m时停止，d为递归的深度（从0开始计数）

2. 总数计算公式 #

函数创建的数组总数由两部分组成：

• 所有递归层中生成的子数组（chunk）数量：即序列k₀到k_d的和
• 所有递归层中创建的结果数组（result变量）数量：共有d+1个（每个递归调用都会创建一个result数组）

因此，总数公式为：

getNumArrays(n, m) = (k₀ + k₁ + ... + k_d) + (d + 1)

3. 递归形式的公式 #

也可以用递归函数来表达这个逻辑，更直观：

def getNumArrays(n, m):
    k = (n + m - 1) // m  # 等价于向上取整ceil(n/m)
    if k <= m:
        return k + 1  # k个chunk + 1个result数组
    else:
        # 当前层的k个chunk + 1个result数组 + 递归处理k个chunk集合的总数
        return k + 1 + getNumArrays(k, m)

独立于n大小的高效算法 #

虽然n的大小会影响序列的长度，但由于每次迭代中k_i都会缩小到原来的1/m左右，迭代的次数是O(log_m n)级别的（比如m=5时，即使n=10^9，迭代次数也仅约12次）。因此我们可以用一个简单的迭代算法来计算，时间复杂度几乎是常数：

def getNumArrays(n, m):
    total_chunks = 0
    result_count = 0
    current = n
    while True:
        k = (current + m - 1) // m
        total_chunks += k
        result_count += 1
        if k <= m:
            break
        current = k
    return total_chunks + result_count

泛化到最大长度为m的情况 #

上面的公式和算法已经完全泛化到任意m（每个数组的最大长度）的场景，只需要将参数m替换为目标最大长度即可。

对您推导思路的补充 #

您提到的32×32×32的模式可能是误解了函数的行为：函数并不会复制数组，而是对数组进行分块拆分。比如当n=32、m=5时，实际的总数是7+2+2=11（7个初始chunk、2个递归chunk，加上2个result数组），而非您推导的较大数值。

内容的提问来源于stack exchange，提问作者Lance Pollard