complexity-theory

5calore

1risposta

Complessità computazionale della conversione di base

Qual è la complessità della conversione di un numero n bit molto grande in una rappresentazione decimale? Il mio pensiero è che l'algoritmo elementare della divisione intera ripetuta, prendendo il res

7calore

2risposta

Questo algoritmo dovrebbe essere eseguito in O (n)?

Nota: Questo è problema 4,3 da Cracking Intervista Coding 5th Edition Problema: Dato un ordinato (ordine crescente) array, scrivere un algoritmo per creare un albero binario di ricerca con l'altezza m

5calore

2risposta

Complessità in un algoritmo di ricorsione

Attualmente sto studiando le strutture dati all'università e mi sono imbattuto in una domanda sulla complessità nella ricorsione. Dato questo codice: Unsigned func (unsigned n) { if (n ==0) return 1

5calore

4risposta

Soluzione ottimale per la "celebrità" algoritmo

Tra n persone, una "celebrità " è definito come qualcuno che è conosciuto da tutti, ma non conosco nessuno. Il problema è identificare la celebrità, se ne esiste una, chiedendo solo la domanda del mod

5calore

2risposta

Quale sarà la complessità di questo codice?

Il mio codice è: vector<int> permutation(N); vector<int> used(N,0); void try(int which, int what) { // try taking the number "what" as the "which"-th element permutation[which] = what;

5calore

3risposta

Perché la complessità cilindrica di questa funzione 12?

Ho una funzione (C#) che controlla quattro serie di condizioni e restituisce un valore bool. Se uno di essi è vero, restituisce true. Sono sicuro di poter semplificare la logica ma voglio che sia abba

5calore

1risposta

Come calcolare la complessità di una funzione ricorsiva?

Qual è il modo più intuitivo per calcolare la complessità di tempo e spazio (notazione O grande) della seguente funzione ricorsiva? function count(str) { if (str.length <= 1) { return 1;

7calore

2risposta

Problemi di partizione Algoritmo della forza bruta

Sto cercando di eseguire lo pseudocodice per il problema della partizione di seguito in bruteforce. un insieme di interi X e un intero k (k> 1). Trova k sottoinsiemi di X tali che i numeri in ogni sot

6calore

1risposta

Ricerca di un elemento a log (n)

mi sono imbattuto alla seguente domanda: Supponiamo che io modifico un determinato elenco ordinato dei numeri distinti 4n come segue: Conservare gli elementi in posizione pari (posizioni 2, 4, 6, ...

5calore

3risposta

Come ottenere Omega (n)

Ho la formula a (n) = n * a (n-1) +1; un (0) = 0 Come posso ottenere l'Omega, Theta o notazione O da questo senza il teorema o Qualcuno avere un buon sito per comprendere la spiegazione