Ordina una serie di n numeri tra [0,2k], dove esiste una coppia tra: | Ai-Aj |> = k/n

Question

Lascia che A1,A2,...,An sia numeri reali tra [0,2k] (k è costante). È noto che per qualsiasi coppia di Ai,AJ quindi |Ai-Aj|>=k/n,

Descrivere un algoritmo che ordina i numeri nella peggiore delle ipotesi di runtime O(n).

So che la risposta dovrebbe essere bucket-sort. Non riesco a capire perché, E in caso affermativo, come faccio a scegliere la quantità corretta di benne? In che modo aiuta lo |Ai-Aj|>=k/n?

Answer 1

La condizione | A _i - A _j | ≥ k/n significa che se dividi l'intervallo [0, 2k] in 2 diversi bucket (ognuno dei quali ha dimensione 2k/2n = k/n), allora ci può essere al massimo un numero in ogni intervallo (tranne forse se i numeri si trovano ai punti finali dei bucket.) Se si creano i bucket in modo più stretto (ad esempio, creando 3n bucket), ciascun bucket ha una dimensione inferiore a k/n e pertanto può contenere al massimo un numero.

È quindi possibile ordinare i numeri utilizzando un algoritmo bucket sort:

• creare un array di benne 3n, ognuno dei quali rappresenta la gamma [(2k/3n) i, ​​(2k/3n) (i + 1))
• Per ogni numero:
  • Dividere questo numero per (2k/3n) per determinare in quale bucket posizionarlo.
  • Inserire il numero in quel bucket.
• Per ciascun segmento:
  • Se quel secchio non è vuota, scrivere il numero in quel secchio nell'array risultato.

Il primo passaggio richiede O (n), in quanto si sta creando un array di dimensione 3n. Il prossimo passo richiede O (n), dal momento che visiti ciascuno dei numeri O (n) una volta e fai O (1) a ogni passo. Anche il passaggio finale richiede O (n) di tempo, poiché stai visitando un totale di 3n bucket.

Spero che questo aiuti!