Рассчитать сложность алгоритма - PullRequest
Новая
       61

Рассчитать сложность алгоритма

0 голосов
/ 15 мая 2018

Я написал этот алгоритм, который имеет O(logn) сложность. Первое время цикла входит в arrayList, пока он не найдет элемент с правильным значением и сложностью. Я организовал arraylist как куча. Во втором случае элементы массива переупорядочиваются в соответствии с их приоритетом. Имеет первый цикл сложности O(n) O(logn)? 

  public void increasePriority(T value, int oldPriority, int newPriority) throws PriorityQueueException {
    if (c.compare(oldPriority, newPriority) > 0) 
        throw new PriorityQueueException("The new priority is lower than the current one");
    int i = getSize() - 1;
    while (i > 0 && !(queue.get(i).getPriority() == oldPriority && queue.get(i).getValue() == value)) {
      i = getParent(i);
    }
    if (i == 0) throw new PriorityQueueException("Element (" + value + "," + oldPriority +") doesn't exits in the queue");
    queue.get(i).setPriority(newPriority);
    while (i > 0 && c.compare(queue.get(i).getPriority(), queue.get(getParent(i)).getPriority()) > 0) {
      swap(i, getParent(i));
      i = getParent(i);
    }
  }

1 Ответ

0 голосов
/ 15 мая 2018

Если ваш arraylist структурирован как куча, то первый цикл имеет сложность O (log n). Он начинается с последнего узла, а затем перемещается вверх по куче. Каждое изменение уровня делит i на 2.

Как написано, ваш increasePriority метод не будет работать, потому что он не обязательно найдет нужный вам узел. Он не смотрит на каждый узел в куче. Например, учитывая эту кучу: 

        1
     2     3
   4   5 6   7

Он начнется с узла 7, затем посмотрим на 3, а затем на 1. Если вы искали какое-либо другое значение, ваш алгоритм его не нашел бы.

Вы должны выполнить последовательный поиск массива, чтобы найти предмет. Затем вы можете использовать второй цикл для изменения приоритета.

То есть находит узел, который нужно изменить, - это O (n). Изменение приоритета, как только вы найдете его, - O (log n). Это делает сложность O (n) + log (n), и поскольку log (n) очень мала по сравнению с n, особенно когда n становится большим, мы называем это O(n).

...