Scegliere il numero m nel miglior tempo possibile

Answer:

The element distinctness problem for lists of numbers is Θ(n log n) and you can reduce it to your problem in constant time by setting m=2 and checking whether the result is 0. So no, O(n log n) is optimal. (See the comments for a caveat, though)

Un po 'più di spiegazione per chi non ha familiarità con l'idea di riduzione: nel problema di distinzione dell'elemento menzionato, ottieni una lista di numeri e devi scoprire se sono distinti, cioè se non ci sono duplicati. Quindi, dati alcuni numeri, come risolvi questo compito? Potresti semplicemente dare i numeri, insieme a m = 2, a qualsiasi algoritmo che risolva il problema di Amen. Se questo ti dice "0", allora sai che c'è un duplicato, e se ti dice qualcosa di più grande, allora sai che non c'è. Quindi se ci fosse un algoritmo per il problema di Amen più veloce di n log n, allora usando il metodo, si potrebbe anche risolvere il problema di distinzione più velocemente di n log n. Ma quel problema è già noto per non essere risolvibile più velocemente di n log n, il che significa che il problema di Amen non lo è nemmeno.

Per buona misura, ecco una implementazione Python dell'algoritmo già menzionato da Amen. Ordina, trova la finestra migliore e mostrala:

m, n, numbers = 4, 6, [10, 12, 10, 7, 4, 22]

numbers.sort()
i = min(range(n-m+1), key=lambda i: numbers[i+m-1] - numbers[i])
print numbers[i:i+m]

Puoi vederlo in azione su ideone . Per trovare solo la differenza, diventa ancora più semplice:

numbers.sort()
print min(high-low for low, high in zip(numbers, numbers[m-1:]))

(sì, amo pubblicizzare Python)

Per fare ciò su un elenco che non è stato ordinato richiederebbe un algoritmo che è peggio di O (n log n), che è il migliore che si possa sperare di ordinare l'elenco in primo luogo, cioè su un unsorted la lista O (n log n) è la migliore.

Tuttavia, va detto che l'ordinamento è un'operazione che deve essere eseguita solo una volta, quindi è possibile ordinare l'elenco e successivamente aggiungere direttamente gli elementi successivi nella sua posizione ordinata per mantenere un elenco ordinato che è un'operazione che richiede solo O (n) tempo. In alternativa, se gli elementi sono inizialmente inseriti in modo tale da mantenere un array ordinato, non sarà necessario eseguire un ordinamento in seguito.

Quindi la vera domanda qui è: qual è il momento migliore per scegliere i m numeri da una serie di n numeri tale che l'insieme di m numeri ha una differenza minima tra max e min dato che l'array n è ordinato ?

Come si vede, questo può essere fatto nel tempo O (n). Lo pseudoalgoritmo è il seguente:

Given array of size n called A_n containing input
Init values currentMin and currentMax
Init values bestDifference and bestDifferenceIndex

for i = 0, i <= n - m
   currentMin = A_n[i]
   currentMax = A_n[i + m - 1]

   if i = 0 or currentMax - currentMin < bestDifference 
       bestDifference = currentMax - currentMin
       bestDifferenceIndex = i

Alla fine di questo usando come input il tuo esempio, bestDifference dovrebbe mostrare 5 e bestDifferenceIndex sarà 0 (l'ordinata A_n sarebbe {5, 7, 10, 10, 12, 22}, il che significa che ha afferrato {5, 7, 10, 10}).

È un po 'fuorviante chiamare questo O (n log n) perché questo non è dovuto all'algoritmo stesso, ma piuttosto al tipo necessario perché l'algoritmo funzioni correttamente e che esegua l'ordinamento ogni volta garantendo comunque di funzionare sempre sarà sicuramente più lento rispetto a quando hai lavorato con un array pre-ordinato e hai evitato la chiamata per ordinarlo del tutto.

Spero che ti aiuti!

Come detto in un'altra risposta, il caso peggiore migliore di O (n log n) non è possibile. Ovviamente puoi provare a essere migliore in alcuni o molti casi.

Calcola il minimo e il massimo. Quindi calcola una dimensione del bucket in modo che qualsiasi gruppo ottimale debba appartenere completamente a due bucket consecutivi e distribuire i valori in quel numero di bucket.

Questo dovrebbe funzionare abbastanza bene con dati casuali.