Indicatori chiave / determinanti che un algoritmo ha una complessità temporale fattoriale o esponenziale?

Question

Indicatori chiave / determinanti che un algoritmo ha una complessità temporale fattoriale o esponenziale?

#1 da (4 voti)

1

Sembra esserci una quantità significativa di informazioni approfondite sulle complessità temporali minori: lineare, polinomiale, logaritmico; Ma non c'è una buona fonte di informazioni approfondite su come determinare facilmente se un algoritmo è o complessità temporale esponenziale o fattoriale. Di solito le risorse hanno informazioni sulla complessità temporale di un algoritmo specifico (ad esempio, il problema del commesso viaggiatore attraverso la ricerca di forza bruta che è O(n!) ), ma nessun modo generale per determinare se un algoritmo è l'uno o l'altro. Qualcuno può fornire modi specifici per determinarlo?

performance algorithms complexity computer-science

posta perseverance 19.05.2017 - 18:48

fonte

1 risposta

Leggi altre domande sui tag performance algorithms complexity computer-science

ogni dispositivo mobile di un nuovo utente diventa un nuovo server - è possibile? Gestione delle richieste errate

score 4 · Answer 1

Un algoritmo esponenziale o fattoriale è uno che è ricorsivo, in cui la profondità della ricorsione è correlata alla dimensione dell'input e una delle seguenti contiene:

Ad ogni livello di ricorsione, l'algoritmo esplora un sottoinsieme di valori più piccolo rispetto al livello superiore. Questo è N!
Ad ogni livello di ricorsione, l'algoritmo esplora lo stesso insieme di valori del livello precedente. Questo è M ** N, dove M è il numero di valori.

Quindi, un esempio di un algoritmo fattoriale sta producendo le permutazioni di un insieme di valori, in cui i valori non vengono riutilizzati:

for (v : values)
    recurse(list.remove(v))

Per confronto, un algoritmo esponenziale che sceglie permutazioni di valori quando puoi riutilizzare i valori:

for (v : values)
    recurse(count - 1, values)

Nel caso precedente, count è la profondità della ricorsione. Quindi per trovare tutte le possibili parole di 3 caratteri formate dai caratteri 'A' e 'B' hai una profondità di 3, che è l'esponente o N (hai una base di 2, per i possibili caratteri).