Как отсортировать двоичный массив в линейном времени?

Question

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

Линейное время означает, что мы должны пройти через массив только один раз, но в соответствии с решением здесь мы первый траверс массива, чтобы найти число нулей, а затем пройти его снова, чтобы заполнить первую часть массива с нулями, а оставшаяся часть с единицами.

Итак, как это линейное решение времени? Какой момент мне не хватает?

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.

Answer 2

В решении массив перемещается дважды. Итак, заказ O(2n) = O(n). Знаки Big-O игнорируют константы. n и 2n оба растут линейно со значением n. Умножение или добавление константы в функцию не изменяет поведение функции.

Answer 3

«Линейное время» означает, что время, требуемое алгоритмом, увеличивается линейно с размером массива. Здесь для каждого элемента, который вы добавляете в массив, у вас есть еще два сравнения (т. Е. 2n).

Answer 4

Говорят, что алгоритм принимает линейное время или время O (n), если его временная сложность равна O (n). Неформально это означает, что при достаточно больших входных размерах время работы увеличивается линейно с размером ввода.

Поскольку этот алогорифм пересекает массив дважды. Он по-прежнему линейный. Подумайте о линейном уравнении y = 2 * x.

Answer 5

O (2n), O (1221n), O (n), O (n/2). Все они линейны. Это означает, что время исполнения всегда меняется постоянно. Так что если у вас есть массив размером 10, например, он всегда будет принимать в два раза больше времени, чем сортировать массив размером 5.

Answer 6

Все общие методы - это линейная временная сложность, то есть O(n). Но напрямую/в-прямо они пересекают один и тот же элемент в массиве дважды, и Водолей (The Asker) ищет одноразовый подход к перемещению.Следующий код пересекает массив один раз и сортирует его во время прохождения.

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--; 
     } 
    } 

Для записи,

О (с * п) = О (п), где с представляет собой постоянную