如何在线性时间内对二进制数组进行排序？

Question

线性时间意味着我们只需遍历数组一次，但根据这里的解决方案，我们将首先遍历数组以找到零的数量，然后再次遍历它以用零填充数组的第一部分和其余部分用 1 表示。

那么，线性时间解是怎样的呢？我错过了什么？

Answer 1

时间复杂度线性时间表示为O(n)。这意味着运行时间随着输入的大小线性增加。一个对数组的所有元素求和的示例，与数组的长度成正比。

具体到您的示例，请查看以下循环Sort()：

int zeros = 0;
for (int i = 0; i < n; i++)
    if (A[i] == 0)
        zeros++;

该循环线性遍历A[]，并对零的数量求和。线性时间也适用于这些循环：

int k = 0;
while (zeros--)
    A[k++] = 0;

// fill all remaining elements by 1
while (k < n)
    A[k++] = 1;

因为你只是穿越A[]一次。

这些操作组合起来就是O(2n)，因为数组被遍历了两次。因此该函数Sort()是一个O(2 * n)操作，相当于O(n)。

这是另一个例子。如果您必须对 100 个二进制数与 10 个二进制数进行排序，哪个会花费更多时间？在这种情况下，对 100 个二进制数进行排序将比对 10 个二进制数进行排序花费 10 倍的时间。这是因为线性时间随输入大小线性增加n。