Domande con tag 'big-o'

domande con tag
3
risposte

Cambiamento della classe di complessità attraverso l'ottimizzazione del compilatore?

Sto cercando un esempio in cui un algoritmo sta apparentemente cambiando la sua classe di complessità a causa del compilatore e / o delle strategie di ottimizzazione del processore.     
posta 26.05.2013 - 15:13
2
risposte

Complessità spaziale di DFS Iterative Deepening

Leggiamo su Wikipedia > Ricerca approfondita approfondita per prima profondità che The space complexity of IDDFS is O(bd), where b is the branching factor and d is the depth of shallowest goal. Wikipedia fornisce anche qualche pseud...
posta 10.09.2011 - 20:56
2
risposte

La "sub-lineare" può ancora essere una linea retta?

Sto lavorando su un problema che richiede una soluzione "sub-lineare". Una ricerca rapida di sub-lineare restituirà molto di questo ... ...dovelalineasub-lineareèmodellatacome logaritmica / asintotica. Ma ero giunto alla conclusione...
posta 25.04.2017 - 04:37
2
risposte

Qual è la complessità temporale dell'aggiornamento nell'heap binario?

Per un heap binario abbiamo O (log (n)) per l'inserimento, O (log (n)) per eliminare min e la costruzione dell'heap può essere eseguita in O (n). Nel contesto dell'utilizzo di un heap binario in Djikstra, il mio esame ha coinvolto un "aggiorn...
posta 16.11.2015 - 07:56
8
risposte

Quanto è significativa la complessità temporale di Big-O di un algoritmo?

I programmatori parlano spesso della complessità temporale di un algoritmo, ad es. O (log n) o O (n ^ 2). Le classificazioni della complessità del tempo sono fatte quando la dimensione dell'ingresso va all'infinito, ma non si utilizza una dim...
posta 11.04.2013 - 01:17
3
risposte

Domanda di runtime del ciclo

Ho fatto un esame oggi e sento di aver fatto abbastanza bene, tranne che non potevo per la vita di me capire quella che sembra essere una domanda incredibilmente semplice. Ci è stato chiesto di fornire tempi di esecuzione della notazione thet...
posta 06.11.2014 - 22:45
5
risposte

Modo efficiente per calcolare quanti oggetti distruggere se ognuno ha una probabilità del 70% di essere distrutto

Iniziamo con una variabile che contiene un numero intero per il "numero di elementi" che abbiamo da qualche parte, in qualche modo. Quindi viene applicato l'algoritmo: ognuno di questi elementi ha una probabilità del 70% di essere distrutto....
posta 20.07.2016 - 21:47
3
risposte

È O (log n) + O (log n) = O (n)? [duplicare]

Sappiamo che la ricerca binaria richiede O (log n) nella notazione Big O ma se abbiamo bisogno di eseguire due volte un algoritmo di O (log n) , sarebbe essere uguale a O (n) in termini di complessità? Ad esempio, se ho un metodo per c...
posta 15.09.2015 - 21:49
2
risposte

Che cosa significa "limite superiore" nel contesto di BigO?

Il mio insegnante di informatica dice che Big O ha un limite superiore ma nessun limite inferiore. Quando guardo un grafico di un algoritmo mappato usando BigO, non c'è affatto un limite superiore. Il limite superiore va avanti all'infinito. Qui...
posta 26.09.2014 - 21:18
1
risposta

In che modo l'hashing del cuculo garantisce O (1) ricerche in presenza di collisioni hash persistenti

La maggior parte delle implementazioni della tabella hash garantiscono O (1) caso medio ma O (n) valore massimo per la ricerca (dove 'n' è il numero di chiavi nella tabella). Ma Cuckoo Hashing è descritto come O (1) massimo. Apparentemente que...
posta 01.04.2016 - 14:33