Julia列优先回代函数col_bs的FLOP浮点运算量计数推导问题

你前面的步骤1~5的运算量拆分逻辑完全正确，问题只出在最后一步的求和化简环节，核心错误是把求和的哑变量j当成了独立于n的自由变量，错误提取到了求和符号外，才得到了不符合预期的结果。

正确化简过程 #

你的总运算量公式是完全正确的：
$$总FLOP = 1 + \sum_{j=2}^n \left( 1 + \sum_{i=1}^{j-1} 2 \right)$$
拆分后得到：
$$总FLOP = 1 + \sum_{j=2}^n 1 + 2\sum_{j=2}^n \sum_{i=1}^{j-1}1$$

分步计算各部分： #

1. 先算$\sum_{j=2}^n 1$：这部分是外层循环的除法运算次数，从j=2到j=n共$n-1$次，加上最后x[1]的1次除法，总共$n$次除法，属于低阶项。
2. 再算双重求和部分$\sum_{j=2}^n \sum_{i=1}^{j-1}1$：这是内层循环的执行总次数，j=2时执行1次、j=3时执行2次……j=n时执行n-1次，本质是首项1、末项n-1的等差数列求和：
   $$\sum_{j=2}^n (j-1) = \frac{n(n-1)}{2}$$
3. 乘以内层单轮循环的2次FLOP（1乘1加）：
   $$2 \times \frac{n(n-1)}{2} = n^2 -n$$

合并结果： #

把所有部分加总：
$$总FLOP = 1 + (n-1) + n^2 -n = n^2$$
只保留最高阶项的话，低阶的n次除法可以直接忽略，最终复杂度就是$O(n^2)$，和三角系统求解的通用结论完全一致。

原推导错误说明 #

你之前的化简中直接将$\sum_{j=2}^n \sum_{i=1}^{j-1}2$等价为$n(j-1)$，这是不成立的：j是外层循环的迭代变量，每一轮取值都会变化，属于求和过程中的临时哑变量，不能作为常量提到求和符号外面，必须按等差数列求和计算才能得到正确的平方阶项。

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