приращения бесконечного двоичный счетчик

Question

Взятые из кодирования интервью:

Как бы реализовать бесконечный двоичный счетчик с increment в O (1) время сложности?

Я думал рассчитать первое и второе положение самого правого 0, но я не уверен, как это реализовать.

«Бесконечный счетчик» означает, что вы можете увеличивать бесконечное количество раз (больше MAX_INT).

Answer 1

Моя попытка:

мы сохраняем агрегацию по последовательному 1 или 0.

означает 111000111 является < 1,0> < 3,1> < 3,0> < 3,1>

Я могу представить это следующим DS:

Список Node {разряд: bool, counter: long}

1) если первый объем составляет 1. он превращается в большую часть 0 `s и поворачивается на следующее 0 до 1.

Теперь мы проверяем, можем ли мы объединить объёмы 1-го.

2) если первая масса равна 0, мы делаем первую цифру 1. и видим, можем ли мы объединить 1.

Пример А:

означает 111000111 является < 1,0> < 3,1> < 3,0> < 3,1>

чтение: три 1 цифры, три цифры 0, три 1 цифры, одна 0 цифры

приращение()

< 1,0> < 3,1> < 2,0> < 1,1> < 3,0>

Пример Б:

< 1,0> < 3,1> < 1,0> < 3,1 >

приращение()

< 1,0> < 3,1> < 1,1> < 3,0>

Aggregat иона:

< 1,0> < 4,1> < 3,0>

Там всегда будет сопз количество изменений (до самого правого 0 цифр)

и Turnning массы 1 s просто переводит булев элемент. который является постоянным

Answer 2

Для двоичного счетчика ...

Если вы хотите сохранить счетчик в «нормальном» битов, вы не можете, принципиально - по крайней мере, не для всегда O (1) а не амортизировано O (1).

Если это бесконечный счетчик, он может иметь произвольно много бит. Это означает, что у вас может быть несколько N бит, все из которых равны 1. Приращение этого счетчика означает установку всех этих битов в 0, что можно разумно считать операцией O (N).

Единственная причина, по которой мы можем считать, что инкремент O (1) в «нормальных» вычислениях обычно связан с типами фиксированного размера, где мы можем сказать (например) «Не более 32 бит необходимо будет изменить - это константа, поэтому, возможно, операция O (1) ».

Для всего прилавка ...

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

Например, в C#:

public DodgySolution 
{ 
    public static DodgySolution Zero = new DodgySolution(null); 

    private DodgySolution tail; 

    private DodgySolution(DodgySolution tail) 
    { 
     this.tail = tail; 
    } 

    // This bit is O(1) 
    public DodgySolution Increment() 
    { 
     return new DodgySolution(this); 
    } 

    // This bit isn't... 
    public BigInteger ToBigInteger() 
    { 
     return tail == null ? BigInteger.Zero 
          : BigInteger.One + tail.ToBigInteger(); 
    } 
} 

Даже это предполагает, что ссылка назначение O (1), хотя - который мог бы стать сложным с бесконечным числом объектов ...

Answer 3

• Используйте какое-то хранилище массивов с удвоенной стратегией. Это означает, что ассигнования амортизируются O (1)
  Связанный список также должен работать.
• Используйте тривиальный учебник. Для более высоких бит перенос экспоненциально редкими. Средняя стоимость переводов составляет 1 + 0,5 + 0,25 + ... = 2, которые O (1)

Таким образом, реализация в прямом направлении амортизировала производительность O (1). Единственная проблема в том, что вам нужно изменить хранилище.

При просмотре отдельных операций приращения числа n, тогда среднее время равно O (1), но наихудшим случаем является O (log (n)). Использование памяти - O (log (n)).

var counter=new List<bool>{false}; 

void Inc() 
{ 
    while(counter[i]) 
    { 
     counter[i]=false; 
     i++; 
    } 
    if(i==counter.Length) 
    counter.Add(true); 
    else 
    counter[i]=true; 
} 

Answer 4

Если вопрос только просить приращения O (1) счетчика без каких-либо других ограничений, ваш счетчик может быть реализован в виде связанного списка чисел и суммы элементов является значение вашего счетчика.

Приращение будет эквивалентно добавлению 1 к последнему элементу или добавлению нового элемента = 1, если значение before больше (Max-1).

Поскольку вы всегда будете проверять 2 пунктов в списке в лучшем случае, то увеличивающийся будет О (1)

Только не пытайтесь делать другое arithmentic с новеньким счетчиком: D