Ordinamento del limite inferiore nel modello di confronto (problema di dadi e bulloni)

1

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.

  1. Dimostra che nel peggiore dei casi, sono necessari i test del dado Ω (n log n) per abbinare correttamente i dadi e i bulloni.
  2. 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:

  1. 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)
  2. Simile al primo, log (n * (n-1) ... (n-k + 1)) = Ω (k log n), quindi dove si trova il n vieni?
posta Mufei Li 12.10.2016 - 02:40
fonte

0 risposte

Leggi altre domande sui tag