Articles of tempo complessità

Che tipo utilizza Java Collections.sort (nodes)?

Penso che sia MergeSort, che è O (n log n). Tuttavia, il seguente output non è d’accordo: -1,0000000099000391,0000000099000427 1,0000000099000427,0000000099000346 5,0000000099000391,0000000099000346 1,0000000099000427,0000000099000345 5,0000000099000391,0000000099000345 1,0000000099000346,0000000099000345 Sto classificando un nodelist di 4 nodes per numero di sequenza, e l’ordinamento sta facendo 6 confronti. Sono perplesso perché 6> (4 log (4)). Qualcuno può spiegarmelo? PS È un mergesort, ma […]

Cache LRU in Java con operazioni Generics e O (1)

Questa è una domanda che emerge molto nelle interviste di lavoro. L’idea è di definire una struttura dati invece di usare LinkedHashMap di Java. Una cache LRU cancella la voce meno recente utilizzata per inserirne una nuova. Quindi, dato il seguente scenario: A – B – C – D – E Dove A è l’elemento […]

Perché la complessità temporale di entrambi DFS e BFS O (V + E)

L’algoritmo di base per BFS: set start vertex to visited load it into queue while queue not empty for each edge incident to vertex if its not visited load into queue mark vertex Quindi penserei che la complessità del tempo sarebbe: v1 + (incident edges) + v2 + (incident edges) + …. + vn + […]

La complessità temporale di contiene (object o), in una lista array di oggetti

Come dice il titolo, mi chiedevo quale sia la complessità temporale del metodo contains () di ArrayList.

Qual è la complessità di questo semplice pezzo di codice?

Sto incollando questo testo da un ebook che ho. Dice la complessità se O (n 2 ) e dà anche una spiegazione per questo, ma non riesco a vedere come. Domanda: qual è il tempo di esecuzione di questo codice? public String makeSentence(String[] words) { StringBuffer sentence = new StringBuffer(); for (String w : words) […]

Complessità temporale di un algoritmo ricorsivo

Come posso calcolare la complessità temporale di un algoritmo ricorsivo? int pow1(int x,int n) { if(n==0){ return 1; } else{ return x * pow1(x, n-1); } } int pow2(int x,int n) { if(n==0){ return 1; } else if(n&1){ int p = pow2(x, (n-1)/2) return x * p * p; } else { int p = […]

Ci sono casi in cui si preferirebbe un algoritmo di complessità del tempo maggiore di livello O su quello inferiore?

Ci sono casi in cui si preferisce la complessità temporale O(log n) alla complessità temporale O(1) ? O O(n) a O(log n) ? Hai qualche esempio?

La complessità del tempo dell’algoritmo Sieve of Eratostene

Da Wikipedia: La complessità dell’algoritmo è operazioni di bit O(n(logn)(loglogn)) . Come si arriva a questo? Che la complessità includa il termine loglogn mi dice che c’è un sqrt(n) da qualche parte. Supponiamo che io stia eseguendo il setaccio sui primi 100 numeri ( n = 100 ), partendo dal presupposto che la marcatura dei […]

come calcolare la complessità della ricerca binaria

Ho sentito qualcuno dire che dal momento che la ricerca binaria dimezza l’input richiesto per la ricerca, quindi è log (n) algoritmo. Dal momento che non provengo da un background matematico, non sono in grado di relazionarmi ad esso. Qualcuno può spiegarlo in modo un po ‘più dettagliato? deve fare qualcosa con la serie logaritmica?

C’è qualcosa che garantisce un tempo costante per accedere a una proprietà di un object in JavaScript?

Questo è per quanto riguarda un dibattito che ho avuto con un intervistatore quando intervistavo Amazon. Creiamo un object: var Obj = {}; Obj[‘SomeProperty’] = function ( ) { console.log(“Accessed some property”); }; Obj[69] = true; C’è qualcosa nella garanzia JavaScript che quando Obj[‘SomeProperty’] successivamente a quelle 2 proprietà come Obj[‘SomeProperty’] e Obj[69] i rispettivi […]