Можно ли как-нибудь сделать этот метод O (1) в Big-O? - PullRequest
Новая
       17

Можно ли как-нибудь сделать этот метод O (1) в Big-O?

1 голос
/ 29 марта 2019

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

Функция моего метода - переместить элементы массива вниз на один, чтобы можно было изменить элемент [0].

Я только что попытался изменить ситуацию, но не могу придумать, как это сделать, не используя array.length (что, как мне кажется, делает O (n). 

@Override
public Object enqueueFront(Object element) {
    expandCapacity();

    for (int i = elementData.length - 1; i > 0; i--) {
        elementData[i] = elementData[i - 1];
    }

    return elementData[0] = element;
}

Я ожидаю, что метод сделает current = current - 1 (см. Код для более подробной информации), чтобы новый элемент мог быть добавлен к первому элементу в массиве без удаления какой-либо информации из текущего массива.

Ответы [ 3 ]

2 голосов
/ 29 марта 2019

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

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

2 голосов
/ 29 марта 2019

Да, если вам разрешено изменять используемую структуру данных.

Вы можете использовать связанный список, это будет выглядеть примерно так 

/* 
   enqueue()
   adds newItem to back of this Queue
   pre: none
   post: !isEmpty()
*/
public void enqueue(Object newItem) {
    Node p = new Node(newItem);
    if (isEmpty()) {
        head = tail = p;
    } else {
        tail.next = p;
        tail = p;  // instead of p = tail;
    }

}
0 голосов
/ 29 марта 2019

Если вы отрегулируете метод expandCapacity для расширения массива с обеих сторон и сохраните index первого элемента, чтобы сделать это следующим образом: 

@Override
public Object enqueueFront(Object element) {
    expandCapacity();

    elementData[indexFirst - 1] = element;
    indexFirst = indexFirst - 1;    

    return;
}

Эта реализация O (1).

@ Генри дал более подробное объяснение сложности времени эквивалентного подхода.

...