请问该priorityQueue析构函数的时间复杂度是O(n)还是O(n²)？

嘿，我来帮你澄清这个疑问！你的判断其实是对的——这个实现的析构函数时间复杂度确实是O(n²)，下面我一步步给你拆解原因：

首先，先看你提供的关键代码片段：

~priorityQueue() {
    for(temp = head; temp->next != NULL; temp = temp->next) {
        extractMin();
    }
}

double extractMin() {
    if (head == NULL) // do nothing
    min = findMin(head);
    else if(min == head) {
        head = head->next;
        // 其他删除节点的操作...
    }
    // 剩余代码...
}

我们逐个分析各步骤的时间开销：

• findMin()的时间：你提到它是遍历双向链表找最小值，这意味着每次调用findMin()都要遍历当前链表中所有剩余的节点，时间复杂度是O(k)，其中k是当前链表的节点数。
• extractMin()的时间：它的核心开销来自findMin()，后续的删除节点操作在双向链表中是O(1)（因为找到节点后，通过prev/next指针调整链接即可），所以extractMin()整体时间复杂度等于findMin()的开销，也就是O(k)。
• 析构函数的总时间：析构函数会调用n次extractMin()（因为总共有n个节点需要移除）。第一次调用时链表有n个节点，开销O(n)；第二次调用时链表剩n-1个节点，开销O(n-1)；……最后一次调用时剩1个节点，开销O(1)。把这些加起来就是：

  n + (n-1) + (n-2) + ... + 1 = n(n+1)/2
  

  这个结果的渐近时间复杂度就是O(n²)。

简单来说，因为每次移除最小值都要重新遍历整个剩余链表，重复n次这样的遍历，就导致了平方级的时间开销。

内容的提问来源于stack exchange，提问作者Josh Garza