按1:9划分数组的树层级计算方法正确性验证问询

问题背景 #

假设某划分算法始终将规模为n的输入数组按1:9的比例划分，需确定当所有子数组规模均为1时对应树的总层级数。

推导过程验证 #

你的推导逻辑和代数运算完全正确：

1. 以每次划分后的较大子数组规模构建等比数列，首项为 9n/10，公比为 9/10。
2. 当子数组规模为1时，列出等式：(9n/10)*(9/10)^(k-1) = 1
3. 推导步骤：

   (9n/10)*(9/10)^(k-1) = 1
   → (9/10)^k * n = 1
   → n = (10/9)^k
   → 取10为底的对数：logn = k * log(10/9)
   → 因log(10/9) = log10 - log9 = 1 - log9，故k = logn/(1-log9)
   

数值代入验证 #

代入n=10时：

• log₁₀10 = 1
• log₁₀9 ≈ 0.9542
• 计算得：k = 1/(1-0.9542) ≈ 21.85，确实约为21或22（取决于近似取整的方式）。

若将初始数组（根节点）算作第1层，总层级数应为k+1（约22.85，向上取整为23），但你的推导中k的定义是从第一次划分后的子数组开始计数的层级数，因此当前数值结果是合理的。

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