Problema: Supponiamo di ricevere n bulloni e dadi di diverse dimensioni, in cui ogni bullone corrisponde esattamente a un dado. Il nostro obiettivo è trovare il dado corrispondente per ogni bullone. I dadi e i bulloni sono troppo simili per poterli confrontare direttamente; tuttavia, possiamo verificare se un dado è troppo grande, troppo piccolo o della stessa dimensione di un bullone.
- Dimostra che nel peggiore dei casi, sono necessari i test del dado Ω (n log n) per abbinare correttamente i dadi e i bulloni.
- Dimostra che nel peggiore dei casi, sono necessari test Ω (n + k log n) per trovare k coppie di corrispondenza arbitrarie.
So come risolvere il primo, ma non ho capito perché Ω (n + k log n) è la risposta nel secondo.
Tentativo:
- L'albero decisionale ha almeno n! foglie raggiungibili, quindi la lunghezza h soddisfa l'equazione che 2 ^ h > = n !, che significa h > = log (n!) = Ω (n log n)
- Simile al primo, log (n * (n-1) ... (n-k + 1)) = Ω (k log n), quindi dove si trova il n vieni?