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

Question

<分区>

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 的大小线性增加。