如何求解下述循环代码的最坏情况时间复杂度？

问题描述 #

给定以下代码：

i = 0;
cin >> a >> b;

while (a <= b)
{
  i++;
  a *= 3; b*= 2;
}

cout << i;

输入两个变量a和b，当a > b时循环退出。每次循环中a乘以3、b乘以2，统计循环次数i。需要分析这段代码的最坏情况运行时间。

推导过程 #

我们可以通过数学建模推导循环次数的上限：
设初始值为a₀（输入的a）、b₀（输入的b），经过k次循环后：

• a的值变为 a₀ * 3ᵏ
• b的值变为 b₀ * 2ᵏ

循环退出的条件是 a₀ * 3ᵏ > b₀ * 2ᵏ，对不等式变形：

(3/2)ᵏ > b₀ / a₀

两边取对数（任意底数均可，比值不变），可得：

k > log(b₀/a₀) / log(3/2)

最坏情况分析 #

最坏情况出现在a₀取最小值（比如a=1）且b₀取极大值的场景。此时不等式简化为：

k > log(b₀) / log(1.5)

这意味着循环次数k与log(b₀)成正比，属于对数级增长。

结论 #

这段代码的最坏情况时间复杂度是O(log b)，并非O(1)。虽然3^k的增长速度远快于2^k，但当b足够大时，循环次数会随b的增大而增加，只是增长速度非常缓慢（对数级）。

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