Limito inferiore per la fusione di array ordinati $ m $ (conteggio delle foglie alberi decisionali - Permutazioni)
-
05-11-2019 - |
Domanda
Ho bisogno di aiuto per capire come calcolare il limite inferiore sulla complessità temporale della fusione $ m $ array ordinati di lunghezza $ n $.
Il limite dovrebbe essere $ nm lg (m) $. Devo dimostrarlo usando un albero decisionale.
Ho provato a contare il numero di possibili permutazioni (che sarebbe stata il numero di foglie nell'albero) ma mi sono bloccato. Ho provato quanto segue:
Quando si fondono il secondo array con il primo, abbiamo $ binom {2n} {n} $ possibilità di posizionare gli elementi. Quando si uniscono il terzo, abbiamo $ binom {3n} {n} $ E così via, quindi il numero totale di permutazioni è:
$$ binom {2n} {n} binom {3n} {n} dots binom {mn} {n} $$
L'altezza dell'albero è indicata $ H $.
$$ h> lg { binom {2n} {n} binom {3n} {n} dots binom {mn} {n}} $$
E da qui non so come dimostrare la complessità.
La mia domanda è: ho considerato correttamente le permutazioni? C'è un limite più semplice? Come continuare da qui?
Inoltre, questo dovrebbe essere probabilmente equivalente al problema di ordinare un $ m $-Aray di dimensioni ordinate $ nm $? Perché in questo problema è facile dimostrare che il limite è $ nm lg (m) $.
Nessuna soluzione corretta