已知算法各迭代步计算量，如何推导其大O表示的最坏时间复杂度？

步骤1：写出总计算量表达式 #

• 最坏情况下每轮迭代的计算量等于当前待处理的问题规模，因此总计算量可以写成：
  T(n) = n + floor(n/2) + floor(n/4) + floor(n/8) + ... + 1
• 你给出的示例n=25时，T(25)=25+12+6+3+1=47，完全符合上述累加规则。

步骤2：去除向下取整求上界 #

由于floor(x) ≤ x恒成立，我们可以直接去掉向下取整得到T(n)的上界：
T(n) ≤ n + n/2 + n/4 + n/8 + ... + 1

步骤3：等比数列求和计算 #

上面的式子是首项为n、公比为1/2的等比数列，根据等比数列求和公式：

等比数列和 S = a₁ × (1 - qᵏ) / (1 - q)，其中a₁为首项，q为公比，k为项数
代入参数a₁=n、q=1/2后计算得：
S = n × (1 - (1/2)^k) / (1 - 1/2) = 2n × (1 - (1/2)^k)
迭代到最后一轮时计算量为1，因此(1/2)^k × n ≈ 1，即(1/2)^k ≈ 1/n，代入上式可得S ≈ 2n - 2，总计算量始终小于2n。

步骤4：转换为大O表示 #

大O表示只关注函数增长的最高阶，忽略常数系数和低阶项，因此T(n) ≤ 2n可以简化为 O(n)。

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