n ° il più piccolo numero tra due database di dimensione n ciascuno utilizzando divide e conquista

Question

abbiamo due database di dimensione n contenenti numeri senza ripetizioni. Quindi, in totale abbiamo 2n elementi. È possibile accedervi tramite una query a un database alla volta. La query è tale da dargli un k e restituisce kth la voce più piccola in quel database. dobbiamo trovare l'ennesima voce più piccola tra tutti gli elementi 2n nelle query O (logn). l'idea è usare divide et impera ma ho bisogno di aiuto per riflettere su questo. Grazie!

Answer 1

Ecco come ho riflettuto. Dato che si tratta di un problema educativo, ti suggerisco di smettere di leggere se qualcuno dei punti ti fa pensare: "aha, non ci avevo pensato, posso pensare più avanti da solo".

1) Stessa osservazione di sdcwc: con un possibile leggero cavillo sul fatto che inizi a 0 o 1, il database può essere pensato come una matrice ordinata. Chiedo l'elemento 0, ottengo il più piccolo. Chiedo per 12, ottengo il 13 più piccolo. E così via. Trovo questo più facile da visualizzare.

2) Sappiamo che stiamo cercando un algoritmo O (log n). Ciò significa che in linea generale stiamo cercando una delle due cose:

• O noi iniziare calcolando il più piccolo elemento, quindi calcolare il secondo più piccolo, più piccolo 4 °, 8 °, ecc, fino a quando siamo in su alle dimensioni che vogliamo, ogni passo in un tempo costante. Questo non mi sembra promettente.

• Oppure iniziamo con un problema di dimensione n quindi eseguiamo un'operazione a tempo costante che ci consente di risolvere il problema originale risolvendo un problema di dimensione n/2.Ovviamente possiamo risolvere il problema per n = 1 in tempo costante, per completare l'algoritmo. Questo suona un po 'più plausibile.

In realtà non deve essere necessariamente n/2 ogni volta. Potrebbe essere n/3 o 999 * n/1000 e il risultato sarà ancora O (log n). Ma non c'è niente di male nel cercare prima n/2.

3) Come ridurremo il problema in questo modo? Bene, se siamo in grado di scartare/rimuovere m elementi dall'inizio di un array o l'altro essendo più piccoli del kth più piccolo, allora possiamo trovare il (km) il più piccolo elemento della risultante coppia di array, e sarà il kth il più piccolo degli array originali.

4) Infine, l'osservazione rivoluzionaria è che se il m più piccolo elemento dell'array A è più piccolo del millesimo più piccolo elemento dell'array B, allora quel mesimo elemento di A non può essere il (2m) il più piccolo elemento del due array combinati. È più piccolo di quello (o di uguale valore: non sono sicuro che "nessuna ripetizione" significhi "nessuna ripetizione in ogni database" o "nessuna ripetizione tra i database combinati"), poiché ci sono al massimo 2 * (m- 1) elementi strettamente più piccoli di entrambi gli array combinati.

A meno che non abbia fatto un errore, il resto è la codifica. Con un piccolo argomento in più per tenere conto di off-by-1 quando k è dispari, questa soluzione è in realtà O (log k), che è O (log n) poiché k < = 2 * n.

Answer 2

Ho visto questo problema in un esame di qualifica non molto tempo fa, e puzza come un problema di compiti a casa. Pertanto, fornirò solo due suggerimenti:

• Studio di ricerca binaria, con particolare attenzione alla precisa natura degli invarianti del ciclo. Il libro di Jon Bentley Perle di programmazione ha una buona spiegazione

• Provare a generalizzare gli invarianti per la ricerca binaria.

• Fai un disegno con vari casi particolari:

  • Ogni numero in DB1 è minore di ogni numero in DB2
  • Viceversa
  • DB1 è uguale a DB2
  • Ogni numero in DB2 è il doppio il numero corrispondente in DB1

Questo è un problema abbastanza difficile; Avrai un tempo più facile se vai dritto per una prova di correttezza.

Answer 3

Punte:

• osservare il vostro "banche dati" sono in realtà due array ordinati.
• Prendere gli elementi da "mezzo" degli array e confrontarli. Il risultato del confronto potrebbe consentire di "escludere" alcune parti.