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:
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?
Non dovresti restituire 'combinazioniOf (n - 1, k - 1) + combinazioniOf (n - 1, k)'? – Blender
@ Blender- Oh, whoops! Sì, risolto. :-) – templatetypedef