Слияние K отсортированных связанных списков, почему сложность O (N * K * K), а не O (N * K) - PullRequest
Новая
       10

Слияние K отсортированных связанных списков, почему сложность O (N * K * K), а не O (N * K)

0 голосов
/ 24 ноября 2018

У меня есть следующее решение, но я слышал от других рецензентов, что это O(N * K * K), а не O(N * K), где N - это (максимальная) длина списков K, а K - этоколичество списков.Например, учитывая списки [1, 2, 3] и [4, 5], N равно 3, а K равно 2. 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    private void advance(final ListNode[] listNodes, final int index) {
        listNodes[index] = listNodes[index].next;
    }

    public ListNode mergeKLists(final ListNode[] listNodes) {
        ListNode sortedListHead = null;
        ListNode sortedListNode = null;

        int associatedIndex;

        do {            
            int minValue = Integer.MAX_VALUE;
            associatedIndex = -1;

            for (int listIndex = 0; listIndex < listNodes.length; listIndex++) {
                final ListNode listNode = listNodes[listIndex];

                if (listNode != null && listNode.val < minValue) {                
                    minValue = listNode.val;
                    associatedIndex = listIndex;
                }
            }

            if (associatedIndex != -1) {
                if (sortedListNode == null) {
                    sortedListNode = new ListNode(minValue);
                    sortedListHead = sortedListNode;
                }
                else {
                    sortedListNode.next = new ListNode(minValue);
                    sortedListNode = sortedListNode.next;
                }

                advance(listNodes, associatedIndex);
            }
        }
        while (associatedIndex != -1);

        return sortedListHead;
    }
}

Я считаю, что тело цикла do-while будет иметь место N раз (поскольку условие остановки цикла do-while выполняется, когда самый длинный список был повторен), в то время как тело for цикла do-while цикла будет происходить K раз (listNodes.length), давая O(n * k).

Почему вышеприведенное решение O(n * k * k) взамен?

1 Ответ

0 голосов
/ 24 ноября 2018

Ваш результирующий список будет содержать максимум n * k элементов.Добавление каждого из этих элементов стоит O ( k ) (внутренний цикл выполняет k итераций для проверки заголовка каждого списка).Следовательно, общее время выполнения равно O ( n * k * k ).

...