Какова временная сложность этого приоритетного деструктора очереди? - PullRequest
Новая
       10

Какова временная сложность этого приоритетного деструктора очереди?

0 голосов
/ 25 апреля 2018

Я не уверен, является ли сложность времени O (n) или O (n ^ 2).Может кто-нибудь уточнить, пожалуйста?Я хочу сказать его O (n ^ 2) из-за обхода в деструкторе и обхода в findMin ().

findMin в основном просто перебирает двусвязный список, находит и возвращает минимальное значение.

    ~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;
            head ->prev = NULL;
            double output = min->data;
            delete min;
            return output;
        }
        else if (min == tail)
        {
            double output = min->data;
            tail = tail->prev;
            tail->next = NULL;
            delete min;
            return output;
        }
        else if(min == head && min == tail)
        {
            return min->data;
            tail = NULL;
            head = NULL;
        }
        else
        {
            double output = min->data;
            min->prev->next = min->next;
            min->next->prev = min->prev;
            delete min;
            return output;
        }
    }
...