关于含四层嵌套循环的图像像素平均算法时间复杂度的问询

以下是实现图像2x2像素平均降采样的代码：

for row in range(0, height, 2):
    for col in range(0, width, 2):   
      # Each pixel in the result image use the the average
      # colour of the 2x2 pixels from the original image
      # (i.e. the pixel itself in row,col and pixels in
      # row,col+1  -- row+1,col -- row+1, col+1  
      sumR = 0
      sumG = 0
      sumB = 0
      for r in range(row, row+2):     # r will be row and row+1
        for c in range(col, col+2):   # c will be col and col+1
          sumR += img[r][c][0]
          sumG += img[r][c][1]
          sumB += img[r][c][2]

请问这个算法的时间复杂度是O(height * width)吗？

嘿，这个问题问得特别到位！咱们来一步步拆解这个时间复杂度的计算：

首先看外层的两个循环：

• 第一个for row循环从0到height，步长是2，所以它的迭代次数大概是height/2次（时间复杂度分析里，奇偶带来的微小差异可以忽略，因为常数项不影响最终的大O表示）
• 第二个for col循环从0到width，步长也是2，迭代次数大概是width/2次

再看内层的两个嵌套循环：

• 每一次外层的(row, col)组合，都会触发内层的2次r循环和2次c循环——也就是说，每个外层组合对应4次内层的像素遍历操作

现在把这些次数乘起来：总操作次数大概是 (height/2) * (width/2) * 2 * 2。你算一下就会发现，这些常数系数（1/2、1/2、2、2）刚好相互抵消，最终结果就是height * width次核心的像素RGB值累加操作。

在时间复杂度的大O表示法里，我们只关注最高阶的项，并且会忽略所有常数系数。再往本质上看，这段代码其实是把原始图像的每一个像素都恰好遍历了一次——因为这些2x2的块是不重叠的，刚好覆盖整个图像，每个像素只会被某一个外层循环对应的内层循环处理一次。

所以结论很明确：这个算法的时间复杂度确实是O(height * width)。

备注：内容来源于stack exchange，提问作者Sam Gore