Qual è la complessità di questo ingenuo codice per calcolare le combinazioni?

Il seguente algoritmo ricorsivo è un modo (piuttosto inefficiente) per calcolare n scegliere k:Qual è la complessità di questo ingenuo codice per calcolare le combinazioni?

int combinationsOf(int n, int k) { 
    if (k == 0) return 1; 
    if (n == 0) return 0; 
    return combinationsOf(n - 1, k) + combinationsOf(n - 1, k - 1); 
}

Essa si basa sul seguente intuizione ricorsiva:

enter image description here

Valutare effettivamente questo la funzione richiede MOLTE chiamate di funzione. Ad esempio, Informatica 2 scegliere 2 in questo modo rende queste chiamate:

combinationsOf(2, 2) 
    | | 
    | +- combinationsOf(1, 2) 
    |  | | 
    |  | +- combinationsOf(0, 2) 
    |  | 
    |  +-- combinationsOf(1, 1) 
    |    | | 
    |    | +- combinationsOf(0, 1) 
    |    | 
    |    +- combinationsOf(1, 0) 
    +- combinationsOf(2, 1) 
     | | 
     | +- combinationsOf(2, 0) 
     | 
     +- combinationsOf(1, 1) 
      | | 
      | +- combinationsOf(0, 1) 
      | 
      +- combinationsOf(1, 0)

ci sono molti modi per migliorare il tempo di esecuzione di questa funzione - potremmo utilizzare la programmazione dinamica, utilizzare la forma chiusa formula NCK = n!/(k! (n - k)!), ecc. Tuttavia, sono curioso solo di quanto inefficiente questo algoritmo specifico sia.

Qual è la complessità temporale di questa funzione, in funzione di n e k?

fonte

2013-05-17 templatetypedef

Non dovresti restituire 'combinazioniOf (n - 1, k - 1) + combinazioniOf (n - 1, k)'? – Blender

@ Blender- Oh, whoops! Sì, risolto. :-) – templatetypedef

Sia C(n,k) essere il costo del computing binom(n,k) in quel modo, con

C(0,_) = 1 
C(_,0) = 1

come casi di base.

La ricorrenza è ovviamente

C(n,k) = 1 + C(n-1,k-1) + C(n-1,k)

se prendiamo Oltre ad avere costi 1. Quindi, si può facilmente verificare che

   k 
C(n,k) = 2 * ∑ binom(n,j) - 1 
      j=0

per induzione.

Così per k >= n, il costo è 2^(n+1) - 1, C(n,n-1) = 2^(n+1)- 3, C(n,1) = 2*n+1, C(n,2) = n*(n+1)+1, (e al di là di questo, non vedo formule pulito).

Abbiamo l'ovvio limite superiore di

C(n,k) < 2^(n+1)

indipendente k, e per k < n/2 possiamo grossolanamente stimare

C(n,k) <= 2*(k+1)*binom(n,k)

che dà una molto più piccola bound per piccoli k, quindi nel complesso

C(n,k) ∈ O(min{(k+1)*binom(n,min(k, n/2)), 2^n})

(necessità di c lampada il k per il minimo, dal binom(n,k) diminuisce a 1 per k > n/2).

fonte

2013-05-17 23:50:52

Forse mi manca qualcosa, ma in che modo questa formula si semplifica in 2^{n + 1} - 1 se k> = n? Se k> = n, il teorema binomiale dice che la somma si riduce a 2^n, quindi dovremmo tornare indietro 1 + 2 (2^n) = 1 + 2^{n + 1}. Come si inverte il segno? – templatetypedef

La somma inizia da '1', non da' 0'. Penso che dovrei scrivere meglio '2 * Σ binom (n, j) - 1' e lasciare che la somma inizi da 0. –

Molto elegante! Una domanda: da dove viene questo? Ho lavorato attraverso l'induzione e ho controllato, ma non ho idea di come avrei potuto inventarlo da solo. – templatetypedef

O(2^n)

Quando n per < k si arresta il ricorsione colpendo n = 0 dopo n passi. In ogni livello di ricorsione si chiamano due funzioni, quindi da qui viene il numero 2. Se n > k, la ricorsione nel "ramo destro" viene interrotta premendo k = 0, che è un minor numero di passaggi, quindi si preme n = 0, ma la complessità complessiva è ancora 2^n.

Ma il vero problema è la ricorsione stessa: il limite dello stack verrà raggiunto molto presto.

fonte

2013-05-17 23:43:16 Strix

Qual è la complessità di questo ingenuo codice per calcolare le combinazioni?

risposta

Problemi correlati