La funzione forzante, o forcing function, denotata con , è un componente chiave nelle relazioni di ricorrenza (solitamente equazioni) utilizzate per descrivere la complessità temporale degli algoritmi, in particolare quelli che seguono il paradigma Divide et impera.
In sintesi, la funzione forzante cattura l’essenza computazionale delle operazioni dirette e non ricorsive di un algoritmo Divide et Impera, e il suo confronto con la funzione spartiacque è fondamentale per determinarne la complessità asintotica utilizzando il Master Theorem.
Ruolo e significato di : La funzione forzante racchiude al suo interno tutti i costi non ricorsivi dell’algoritmo. Nello specifico, essa rappresenta la complessità temporale delle fasi di:
Divide (Divisione): Il tempo impiegato per suddividere il problema originale in sottoproblemi.
Combina (Combinazione): Il tempo necessario per combinare le soluzioni dei sottoproblemi per ottenere la soluzione del problema originale.
Prendendo l’esempio del MergeSort, la sua ricorrenza è . Qui, , che rappresenta il costo della procedura Merge (la fase di combinazione) la quale impiega tempo per unire due sotto-array di lunghezza . La fase di divisione (calcolo del centro dell’array) impiega tempo costante, , che è assorbito da .