中点圆算法时间复杂度疑问：O(x-y)、O(1)还是O(r)？

核心疑问 #

学习中点圆算法时，发现不同资料对时间复杂度的表述存在差异：有的资料未提及，有的给出O(x–y)的结论。但x、y是算法迭代中的固定坐标值，由此产生疑问：该算法的时间复杂度到底是O(1)，还是以圆半径r为变量的O(r)？

个人推测 #

• 类比遍历nm二维矩阵的O(NM)，认为中点圆算法的时间复杂度应为O(r)
• 从圆周长度出发，遍历圆周的时间复杂度是O(2πr)，去掉常数后为O(r)
• 若修改算法遍历圆内所有单元格，时间复杂度应为O(πr²)，去掉常数后为O(r²)

明确结论与解释 #

首先要理清算法复杂度分析的核心：复杂度是基于输入规模的变化来衡量的，这里的输入规模是圆的半径r，而非固定的坐标值x、y。

• 标准中点圆算法仅绘制圆周上的像素，利用对称性只需要计算1/8圆周的点，再映射到其他7个对称位置。1/8圆周的像素数量和半径r成线性关系，因此时间复杂度为O(r)。部分资料里的O(x–y)属于表述不严谨，这里的x、y实际是迭代过程中坐标的变化范围，本质仍和r线性相关。
• 若算法用于填充圆（遍历圆内所有像素），则需要处理的像素数量和圆的面积成正比，时间复杂度为O(r²)，你的这个推测完全正确。
• 至于O(1)的说法，仅当半径r是固定不变的常量时才成立，但复杂度分析通常针对输入规模可变的场景，所以标准中点圆算法的时间复杂度是O(r)。

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