基于三色数组重排实例验证Big-O复杂度理解的正确性

你的理解完全正确！这是解决荷兰国旗问题的经典计数法，咱们来详细验证一下你的复杂度分析：

时间复杂度：O(n) #

你的算法执行了两次完整的数组遍历：

• 第一次遍历统计WHITE和BLUE元素的数量，遍历次数为n，时间开销是O(n)
• 第二次遍历根据计数重写数组元素，遍历次数同样为n，时间开销也是O(n)

大O表示法关注的是增长趋势，常数系数会被忽略，因此O(2n)等价于O(n)，完全符合题目要求的线性时间复杂度。

空间复杂度：O(1) #

你的算法只使用了两个固定大小的计数变量numW和numB，它们的内存占用不随数组元素总数n的变化而改变——不管n是10还是10000，额外使用的空间都是恒定的。这种不依赖输入规模的额外空间开销，就是我们说的常数空间复杂度O(1)，满足题目的要求。

顺便提一句，这个解法非常直观，不过荷兰国旗问题还有单遍历的三指针解法（原地交换元素），感兴趣的话可以深入了解，但你的解法已经完美符合题目给出的复杂度要求啦。

你的伪代码格式化后如下：

numW = numB = 0 
for i = 0 to n-1:  // 注：这里建议修正为n-1，避免数组越界
    if ARRAY[i] == WHITE: 
        numW++ 
    else if ARRAY[i] == BLUE: 
        numB++ 
for i = 0 to n-1: 
    if numW > 0: 
        ARRAY[i] = WHITE 
        numW-- 
    else if numB > 0: 
        ARRAY[i] = BLUE 
        numB-- 
    else: 
        ARRAY[i] = RED 

（小提示：原伪代码里的to n可能会触发数组越界，通常数组索引范围是0到n-1，所以这里做了小调整）

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