Come ragionare sulla complessità di Mettere k elenchi concatenati ordinati?

Sto cercando di capire meglio la notazione di Big O per essere in grado di ragionare in modo molto più chiaro e, quindi, ho bisogno di un feedback sulla mia analisi fornita di seguito per un problema: Unisci elenchi concatenati k-ordinati in uno solo.

Rivendicazione n. 1:

var merge2Lists = function(list1, list2) {
        if (!list1) {
            return list2;
        }
        if (!list2) {
            return list1;
        }

        if (list1.val <= list2.val) {
            list1.next = merge2Lists(list1.next, list2);
            return list1;
        }
        else {
            list2.next = merge2Lists(list2.next, list1);
            return list2;
        }
    };

merge2Lists menzionato sopra è utilizzato da entrambe le soluzioni indicate di seguito. La complessità di questa funzione dovrebbe essere O (n1 + n2) dove n1 e n2 sono rispettivamente numero di elementi in list1 e list2. Oppure possiamo solo dire che nel peggiore dei casi entrambe le liste avranno lo stesso numero di elementi e dovremo esaminarli tutti almeno una volta, quindi possiamo chiamarlo O(n) .

Claim # 2

// Solution: 1
var mergeKLists = function(lists) {
    let len = lists.length, interval = 1, i;
    while (interval < len) {
        for (i = 0; i < len; i += interval*2) {
            lists[i] = merge2Lists(lists[i], lists[i+interval])
        }  
        interval *= 2;
    }
    return (len > 0) ? lists[0]: lists;
}

Dire che ho 10 liste nel mio input che devono essere unite. La mia soluzione precedente prende quelle 10 liste e nella prima iterazione del ciclo while, unisce 10/2 = 5 coppie. Nella prossima iterazione, unisce 10/4 = 3 coppie. Quindi unisce 10/8 = 2 coppie e infine abbiamo la nostra lista ordinata finale negli elenchi [0].

Poiché il numero di coppie da unire viene dimezzato a ogni passaggio, la sua complessità temporale dovrebbe essere log(k) , dove k è il numero di elenchi nell'input. Un altro modo per descriverlo può essere che, se raddoppiamo la dimensione dell'ingresso (cioè da 10 a 20), il numero di operazioni aumentate sarà non doppio, il che significa che non è sicuramente O(n) . Il numero di operazioni può aumentare solo di 1, il che significa che dovrebbe essere log(k) .

Insieme alla rivendicazione 1, la complessità totale dovrebbe diventare: O (n * log k) . Non so come spiegarlo chiaramente però.

La complessità dello spazio dovrebbe essere O(1) dato che la nostra memoria rimane costante rispetto alle dimensioni dell'input.

Richiesta n. 3

// Solution: 2
var mergeKLists = function(lists) {
    let len = lists.length;
    if (!len) return lists;

    while (lists.length > 1) {
        lists.push(merge2Lists(lists[0], lists[1]));
        lists.shift();
        lists.shift();
    }
    return lists[0];
};

Qui mergeKLists sta unendo solo 1 coppia in ogni iterazione del ciclo while. Se abbiamo 10 liste, dopo la prima iterazione avremmo fuso solo 1 coppia. Nella seconda iterazione uniremo un'altra coppia e così via. Quindi sembra che stiamo facendo 10 operazioni in totale. Quindi la sua complessità dovrebbe essere O (k) dove k è il numero di liste in input.

Se raddoppiamo la dimensione dell'input da 10 a 20, il numero di operazioni aumentate sarà 10, il che è in linea con la nostra complessità dedotta di O(k) .

Più sopra stiamo usando shift() funzione 2 volte per scartare gli elenchi non necessari dalla matrice. La complessità di shift () stesso è O (m) dove m è il numero di elementi nell'array spostato. Nel peggiore dei casi, lo spostamento dovrà spostare m elementi a sinistra. Quindi la complessità temporale per questa soluzione diventerà O (k + m) .

Insieme alla rivendicazione 1, la complessità totale dovrebbe diventare: O (n * (k+m)) .

La complessità dello spazio dovrebbe essere O(1) come per ogni nuovo elemento che viene spinto nell'array, scartando gli elementi dall'array in cui lo spazio acquisito non aumenta rispetto all'input.

1. Queste affermazioni sono corrette? In caso contrario, puoi gentilmente aiutarmi a capire meglio?
2. Esiste un modo più chiaro per motivo sulle dichiarazioni fatte sopra?
3. Ho notato che almeno su LeetCode Solution # 2 funzionava a 30 ms più veloce della soluzione n. 1 per lo stesso set di casi di test. Può essere solo un bug di LeetCode o Network Latency, in quanto mi aspettavo che la Soluzione n. 1 fosse eseguita molto più velocemente a causa della sua complessità nel tempo di log (k).