时间复杂度T(n)=log₂(n)的算法在千倍速计算机上的求解规模计算

已知条件：

• 算法时间复杂度为 T(n) = log₂(n)，即处理规模n需执行log₂(n)次运算
• 原计算机在时间T内可求解规模为n₁的问题，说明该时间内原计算机能完成log₂(n₁)次运算
• 新计算机运算速度是原计算机的1000倍，相同时间T内可完成1000 * log₂(n₁)次运算

推导过程：
新计算机在时间T内处理规模n₂时，运算次数需等于其总运算能力，因此：

log₂(n₂) = 1000 * log₂(n₁)

根据对数运算性质 k * log_b(x) = log_b(x^k)，将等式右侧转换：

log₂(n₂) = log₂(n₁^1000)

由于对数函数单调递增，两侧真数相等，可得：

n₂ = n₁^1000

举例说明：若原计算机能处理n₁=2的问题，新计算机则可处理2^1000规模的问题，可见对数时间复杂度的算法在提速后的规模提升是指数级的。

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