计算算法的复杂度

Question

我写的这个算法具有 O(logn) 的复杂性。第一个 while 循环进入 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);
    }
  }

Answer 1

如果您的 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).

计算算法的复杂度

Calculate complexity of algorithm

heap

complexity-theory

priority-queue