Notazione Big O di casualità

Naviga le tue risposte
1

Stavo pensando ad algoritmi inefficienti basati sulla casualità e mi sono chiesto come classificarli.

Per esempio. Supponi di voler generare tutti i numeri da 1 a N in ordine casuale ma solo una volta ciascuno.

Il mio algoritmo inefficiente fa questo ... 

Generate a random number between 1 and N (inclusive).
Check it has not already been used.
If it has then generate a new random number until you get one that hasn't been used.
Display the random number.
Store random number in checking array.

Questo dovrebbe ottenere tutti i numeri in un ordine casuale ma per valori elevati di N dovrà essere eseguito più volte quando si ottengono gli ultimi numeri.

Per esempio. In media, l'ultimo valore casuale richiederà N volte per generare.

Il caso migliore per questo è O (N) perché esiste la possibilità che ogni numero casuale generato sia distinto.

Il caso medio è un po 'più difficile ...

Senza andare correttamente nel calcolo penso che sia O (NlogN) o possibile O (N ^ 2).

Ma quale sarebbe il caso peggiore? Bene, il caso peggiore è che non trova mai tutti i numeri. Sarebbe un loop infinito e mai effettivamente completato. Per N di grandi dimensioni è comprensibile, ma come si fornisce la notazione O grande per questo?

    
posta Fogmeister 14.05.2015 - 10:44
fonte

3 risposte

4

Il caso peggiore è O (∞). Il caso migliore è Ω (n 2 ), perché devi generare n numeri e per ogni numero generato devi cercare un elenco di lunghezza n se il numero è già presente.

    
risposta data 14.05.2015 - 11:05
fonte
1

Direi che questo problema sarebbe risolto usando l'analisi probabilistica. Quindi dovresti considerare la probabilità che un numero casuale selezionato fosse già nella lista. Per fare ciò potrebbe essere necessario fare un'ipotesi sul generatore di numeri casuali, in particolare sul fatto che generi numeri con una distribuzione uniforme, il che significa che qualsiasi numero da 1 a N avrebbe ugualmente probabilità di essere generato.

Quindi per il primo numero selezionato la probabilità che sia già stata selezionata è 0 / n = 0, poiché nulla è ancora nella lista. Il secondo numero la probabilità che il numero sia già stato selezionato è 1 / n. Questo dovrebbe continuare con ogni numero generato. Inoltre, dovresti associare i costi a ciascuna di queste probabilità. Dovresti considerare sia i costi associati alla probabilità che il numero sia già stato selezionato sia il costo associato alla probabilità che non lo sia stato.

    
risposta data 20.04.2016 - 06:03
fonte
0

Se si desidera creare un array, è possibile utilizzare un algoritmo leggermente modificato che viene eseguito in O (n). 

Fill the array with the numbers from 1 to n. 
Repeat for i = 0 to n - 1:
    Generate a random number r such that 0 ≤ r < n - i.
    Exchange array [i] and array [i + r]
    
risposta data 20.04.2016 - 09:57
fonte

Leggi altre domande sui tag

Configurazione in fase di compilazione e in fase di esecuzione Perché dovremmo aspettarci che le coroutine dello spazio utente siano più leggere dei thread del sistema operativo?