Domande con tag 'algorithm-analysis'

domande con tag
5
risposte

Algoritmi Divide and Conquer - Perché non dividere in più parti di due?

Negli algoritmi di divisione e conquista come quicksort e mergesort, l'input è solitamente (almeno nei testi introduttivi) suddiviso in due e i due set di dati più piccoli vengono quindi gestiti in modo ricorsivo. Ha senso per me che questo re...
posta 05.05.2013 - 20:21
4
risposte

Quando parlo, come posso dire che l'ordine di complessità temporale di un algoritmo è O (N log N)?

Che termine posso usare per descrivere qualcosa con complessità di O (N log N)? Ad esempio: O (1): costante O (log N): logaritmico O (N): lineare O (N log N): ?????? O (N 2 ): Quadratico O (N 3 ): Cubico
posta 18.07.2015 - 09:01
5
risposte

Algoritmi: come riassumo O (n) e O (nlog (n)) insieme?

Ho il seguente algoritmo che trova i duplicati e li rimuove: public static int numDuplicatesB(int[] arr) { Sort.mergesort(arr); int numDups = 0; for (int i = 1; i < arr.length; i++) { if (arr[i] == arr[i - 1]) {...
posta 08.10.2014 - 22:59
8
risposte

Perché la ricerca binaria, che ha bisogno di dati ordinati, è considerata migliore della ricerca lineare?

Ho sempre sentito che la ricerca lineare è un approccio ingenuo e la ricerca binaria è migliore di quella in termini di prestazioni a causa della migliore complessità asintotica. Ma non ho mai capito perché è meglio della ricerca lineare quando...
posta 10.07.2013 - 09:37
7
risposte

Big Oh notation non menziona il valore costante

Sono un programmatore e ho appena iniziato a leggere Algoritmi. Non sono completamente convinto delle notazioni di Bog Oh, Big Omega e Big Theta. La ragione è per definizione di Big Oh, afferma che dovrebbe esserci una funzione g (x) tale che si...
posta 29.10.2012 - 04:35
2
risposte

Cercando di capire il 2N lNN confronta per quicksort

Stavo passando per l'analisi di quicksort nel libro Algorithms di Sedgewick. Crea la seguente relazione di ricorrenza per il numero di confronti in quicksort mentre ordina un array di N elementi distinti. Mi sto divertendo a capire questo...
posta 11.07.2013 - 12:36
2
risposte

La complessità del tempo di 2 ^ sqrt (n)

Sto risolvendo una domanda sull'algoritmo e la mia analisi è che sarebbe eseguita su O (2 ^ sqrt (n)). Quanto è grande? Corrisponde a O (2 ^ n)? È ancora tempo non polinomiale?     
posta 12.03.2016 - 18:00
1
risposta

Possibile miglioramento di Damerau-Levenshtein?

Recentemente ho implementato l'algoritmo di distanza Damerau-Levenshtein dallo pseudocodice su Wikipedia. Non sono riuscito a trovare alcuna spiegazione su come funziona esattamente e lo pseudocodice usa nomi di variabili completamente disinform...
posta 06.04.2013 - 22:10
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

differenza tra metodi contabili e potenziali nell'Analisi Ammortizzata

Stavo passando per l'Introduzione agli algoritmi di Cormen et al.Nel capitolo intitolato Amortized Analysis, la differenza tra metodi contabili e potenziali è data in questo modo The accounting method overcharges some operations early in th...
posta 15.08.2013 - 14:50