algorithm - 通过具体示例了解 Big-O

Question

我正在研究一个相当简单的问题，以确保我理解这些概念。

问题是:存在一个包含 n 个元素的数组 A，或者是红色，或者是白色，或者是蓝色。重新排列数组，使所有白色元素位于所有蓝色元素之前，所有蓝色元素位于所有红色元素之前。在 O(n) 时间和 O(1) 空间中构建算法。

根据我的理解，该解决方案的伪代码是:

numW = numB = 0
for i = 0 to n:
    if ARRAY[i] == WHITE:
        numW++
    else if ARRAY[i] == BLUE:
        numB++

for i = 0 to n:
    if numW > 0:
        ARRAY[i] = WHITE
        numW--
    else if numB > 0:
        ARRAY[i] = BLUE
        numB--
    else:
        ARRAY[i] = RED

我相信它是 O(n) 因为它运行了两次循环并且 O(2n) 在 O(n) 中。我相信空间是 O(1)，因为它不依赖于元素的总数，即每个元素总会有一个计数

我的理解正确吗？

Answer 1

如果它是线性时间，并且您的算法看起来是线性时间，那么它就是您所怀疑的 O(n)。这里有一个很好的总结:Big-O for Eight Year Olds?