Domande con tag 'complexity'

domande con tag
3
risposte

Analisi della complessità: ricerca di membri comuni di matrici non ordinate

Ho esaminato le precedenti interviste tecniche che ho avuto (ne ho ricevuto un altro in arrivo). Il problema Ad ogni modo, una domanda che ho avuto è stata ... Given 2 unsorted arrays how would you find all of the common objects bet...
posta 23.02.2015 - 12:54
2
risposte

Array vs Dynamic Array

In Manuale di progettazione dell'algoritmo di Edition 2 di Steven Skiena, parla di array dinamici su pagina 67 , che li porta ad avere lo stesso Big-Oh degli array normali. Non capisco come. Questo è ciò che afferma il libro Half the ele...
posta 14.02.2017 - 20:42
3
risposte

Quali sono le conseguenze di Hash-Life in esecuzione in O (log n)?

Dopo aver letto l'algoritmo HashLife , ho scoperto che viene eseguito in O (log n) . The Game of Life è anche Turing Complete , quindi in teoria dovremmo essere in grado di eseguire qualsiasi algoritmo su un "computer" costruito in GoL. Co...
posta 02.04.2014 - 17:42
1
risposta

Qual è la complessità temporale di questo programma?

Viene fornito un algoritmo su GeeksForGeeks.com per la costruzione di un albero di ricerca binario dal suo preorder traversal. Dicono che la complessità temporale per il codice seguente è O (n ^ 2). Ma secondo me dovrebbe essere O (nlogn)....
posta 23.07.2015 - 23:51
1
risposta

Algoritmi di confronto e complessità

Voglio risolvere questo problema: Write a method to return all valid combinations of n-pairs of parentheses. The method should return an ArrayList of strings, in which each string represents a valid combination of parentheses....
posta 21.11.2016 - 23:55
2
risposte

Burrows-Wheeler trasforma la ricerca all'indietro: come trovare l'indice del suffisso?

L'algoritmo di ricerca all'indietro di BWT è piuttosto semplice se abbiamo solo bisogno della molteplicità di un modello. Tuttavia ho anche bisogno di trovare gli indici del suffisso (cioè posizioni nella stringa di riferimento dove si verifica...
posta 22.11.2015 - 02:57
1
risposta

Manutenzione Complessità degli script di build di Gradle

Attualmente sto provando Gradle per il mio progetto di sviluppo embedded. Lo strumento esistente è GNU Make. In Internet ho letto molti articoli in cui le persone dicono che la loro logica di costruzione diventa "troppo complessa" e vorrebbero r...
posta 07.02.2017 - 14:54
4
risposte

Complessità nei cicli nidificati

Premessa: In questo post creerò la confusione comune tra O(n) e Theta(n) come notazioni di complessità. Scriverò pseudo-codice per parlare di algoritmi, usando qualsiasi notazione che trovo di mio gradimento. Lo so, ancora un...
posta 02.01.2014 - 11:53
4
risposte

differenza tra crescita esponenziale e logaritmica

Perché for(k=1;k<=n;k*=2) cresce logarathmically = O(logn) ma lo sento crescere in modo esponenziale, visto che il seq assomiglia a 1,2,4,8.... e per le serie di fibonacci la gente dice che cresce in modo esponenziale. che...
posta 02.02.2014 - 09:17
6
risposte

Perché la definizione formale di notazione Big O è formulata come tale?

Considera la definizione formale: f(n) = O(g(n)) Perché non lo è: f(n) = O(f(n)) o f(n) = O(c*f(n)) dato che per l'analisi Big O, f(n)=2n e g(n)=n sono identici? Sono confuso dalla funzione f(n) che u...
posta 02.10.2011 - 11:25