循环时间复杂度分析咨询：判断我的复杂度推导是否正确

Loop 1 #

代码 #

for (auto i = 1; n > 0; n -= i, i +=2) {}

你的分析 #

结论：时间复杂度为O(n)
理由：i仅呈线性变化，当n趋近于正无穷时，n-i的影响可忽略。

正确结论与推导 #

你的结论错误，实际时间复杂度是O(√n)。
每次循环里，i依次取1、3、5、7……这类连续奇数，而数学上有固定结论：前k个正奇数的和等于k²。循环终止时，这些i的累加和近似等于初始的n，即k² ≈ n，解得k ≈ √n——这就是循环执行的次数，因此时间复杂度为O(√n)。

Loop 2 #

代码 #

for (auto i = 1; n > 0; n -= i, i += i / 2) {}

你的分析 #

结论：时间复杂度为O(n)
理由：i构成等比数列：i_n = i_1 *(3/2)^(n - 1)

正确结论与推导 #

你的结论错误，分两种场景讨论：

1. 整数类型场景：如果i是整数，i=1时i/2=0，因此i始终为1，每次循环仅将n减1，循环执行n次。但你的理由完全错误——此时i并未构成等比数列，而是固定为1。
2. 浮点数类型场景：如果i是浮点数，i会依次变为1、1.5、2.25、3.375……，构成公比为3/2的等比数列。前k项的和为2*((3/2)^k - 1)，当该和接近n时，(3/2)^k ≈ n/2，取对数可得k ≈ log_{3/2}(n)，即循环次数为对数级别，时间复杂度为O(log n)。

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