Domande con tag 'algorithm-analysis'

domande con tag
1
risposta

Il mio ragionamento per determinare il Big-O di questo algoritmo è corretto?

Prendi il seguente algoritmo con due sezioni separate e le sezioni non si influenzano a vicenda (la funzione non è ricorsiva). void algorithm(int x) { // This section of the algorithm has linear growth... O(x) // This section of the alg...
posta 22.04.2018 - 22:07
1
risposta

Coda prioritaria per l'algoritmo di Kruskal con tempo di esecuzione O (E lg V)

Sto rivedendo i miei appunti sull'algoritmo di Kruskal e ho una domanda su come portare il tempo di esecuzione a O (E lg V). Usando un PQ con bordi e un array booleano di cui i vertici abbiamo aggiunto al nostro albero T , il tempo di esecuzi...
posta 06.05.2013 - 14:23
1
risposta

Reverse engineering di un checksum o CRC

Sto cercando di decodificare un checksum o un CRC in cui un numero a 8 bit * viene convertito in un numero a 5 bit per il controllo degli errori. Ho un elenco incompleto di valori e checksum dei dati e ho bisogno di capire l'algoritmo in modo da...
posta 11.04.2018 - 03:02
2
risposte

Loop Invariant in funzione ricorsiva

Durante la lettura di Introduction to Algorithms (3a edizione, P188), c'è un algoritmo chiamato Tail-Recursive-QuickSort e dobbiamo dimostrare la correttezza di questo algoritmo. TAIL-RECURSIVE-QUICKSORT(A, p, r) 1 while p < r 2 // Part...
posta 11.09.2016 - 18:31
1
risposta

Il percorso più breve per visitare tutti i nodi [duplicato]

Mi viene data una serie di attrazioni turistiche (nodi identificati da x, y) e ho bisogno di trovare il percorso più breve per visitarli. Per come la pensavo, ignorerò se ci sono strade disponibili e consideriamo che le strade vanno sempre...
posta 21.12.2014 - 15:38
1
risposta

chiarimenti sull'analisi ammortizzata

Stavo esaminando un articolo qui Nella sezione denominata Metodo aggregato, l'autore dice Then summing over the entire sequence, all the 1's sum to O(n), and all the di also sum to O(n). That is, e poi dà questo Σ1≤i≤n ci ≤ n...
posta 21.06.2013 - 08:02
0
risposte

Assegnazione di tag alle coordinate ottenute rispetto alle coordinate ideali

Ho bisogno di un'idea per risolvere il seguente problema. Qui avremo due serie di coordinate. Il set 1 avrà le coordinate ideali con i tag ad esso assegnati che saranno come di seguito. Set2otterràpuntichepossonoesserepresentiovunquenelsistemad...
posta 21.03.2018 - 09:24
0
risposte

Approccio per il confezionamento di forme 2D riducendo al minimo l'area di chiusura totale

Non sono sicuro sui miei tag per questa domanda, ma in breve .... Ho bisogno di risolvere un problema di imballaggio di parti industriali in casse, riducendo al minimo l'area di contenimento totale. Queste parti sono motori, o pompe, o compon...
posta 19.08.2014 - 19:44
1
risposta

Qual è il tempo di CPU big-O dell'algoritmo di Euclide di "Il più grande divisore comune di due numeri"

Osservando l'algoritmo di Euclid per il "Più grande divisore comune di due numeri", sto cercando di divinare il tempo della CPU O grande per i numeri K e N. Qualcuno può aiutarti? Questo è l'algoritmo perché lo comprendo .. Dove: max (...
posta 27.09.2013 - 15:22
1
risposta

confronti del caso peggiore per l'inserimento di casi speciali sort [chiuso]

Considera un inserimento Ordina con un Sentinel su n valori, dove ogni valore si verifica esattamente due volte nell'input (quindi n deve essere pari). Quindi l'input migliore per i confronti è quando gli elementi sono già ordinati e il numero e...
posta 11.02.2015 - 15:22