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

Question

http://www.techiedelight.com/sort-binary-array-linear-time/

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

那么这怎么是线性时间的解决方案呢？我错过了什么吗？

- Aquarius_Girl

---

O(2n) => O(n)，这是线性的。 - Stargateur

请解释一下 - 我对线性事物的理解可能不够清晰。@Stargateur - Aquarius_Girl

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)。

以下是另一个例子。如果你需要对比10个二进制数和100个二进制数进行排序，哪一个需要更多的时间？在这种情况下，对100个二进制数进行排序将比对10个二进制数进行排序长10倍。这是因为线性时间与输入大小n成正比增加。

- RoadRunner

Answer 2

如果算法的时间复杂度为O(n)，则称其为线性时间或O(n)时间。简单来说，这意味着对于足够大的输入大小，运行时间与输入大小成线性增长。

由于此算法遍历数组两次，因此仍然是线性的。可以将其想象成一个线性方程y = 2*x。

- Dave S

Answer 3

所有分享的方法都具有线性时间复杂度，即O(n)。但是直接或间接地它们会两次遍历数组中的相同元素，而 Aquarius（提问者）正在寻找一次遍历的方法。下面的代码在遍历数组时对其进行排序并仅遍历一次。

int left = 0, right = arr.length - 1;
while (left < right)
    {
        while (arr[left] == 0 && left < right)
            left++;

        while (arr[right] == 1 && left < right)
            right--;

        if (left < right)
        {
            arr[left] = 0;
            arr[right] = 1;
            left++;
            right--;
        }
    }

记录一下，

O(c*n) = O(n)，其中c为常数

- Abhishek

Answer 4

在这个解决方案中，数组被遍历了两次。因此，时间复杂度为 O(2n) = O(n)。大O符号忽略常数。 n 和 2n 都随着 n 的值线性增长。将一个常数乘以或加到一个函数中不会改变函数的行为。

- haccks

---

请解释线性排序的含义。这不是意味着数组只需遍历一次吗？ - Aquarius_Girl

@AquariusTheGirl；在这种情况下，“linear”表示时间复杂度用线性函数表示。 - haccks

Answer 5

“线性时间”意味着算法所需的时间与数组大小成线性增长。也就是说，对于每个添加到数组中的项，您需要进行两次比较（即2n）。

- Mureinik

Answer 6

O(2n), O(1221n), O(n), O(n/2)。所有这些都是线性的。这意味着执行时间始终会不断变化。因此，如果您有一个大小为10的数组，它将始终比对大小为5的数组进行排序需要花费两倍的时间。

- Semyon Tikhonenko

---

这是点号。/ 这是除法。 - Semyon Tikhonenko