OKPEDIA ANALISI COMPLESSITà

Classe di complessità P

Nella classe di complessità P sono compresi i problemi polinomiali deterministici. Il problema può essere risolto dall'elaboratore (algoritmo) in tempi accettabili. L'algoritmo formula una soluzione e la verifica, restituendo un risultato in un tempo polinomiale rispetto al dato di input.

Esempio di problema di classe P. Si ipotizzi di voler calcolare l'insieme dei divisori interi di un numero n. Per individuare l'insieme dei divisori è sufficiente verificare ogni numero intero inferiore o uguale al numero n, effettuare la divisione e verificare se il resto è nullo oppure no. Quanto maggiore è il numero n tanto più lungo sarà il tempo di esecuzione dell'algoritmo che, in ogni caso, formulerà la risposta in un tempo polinomiale rispetto al dato di input.

La classe di complessità P è anche conosciuta come la classe dei "problemi facili" per sottolineare la differenza con l'altra classe di complessità NP ("problemi difficili") nell'analisi della complessità dei problemi.

https://www.okpedia.it/classe_di_complessita_p




Questo sito utilizza cookie tecnici. Sono presenti alcuni cookie di terzi ( Gooogle, Facebook ) per la personalizzazione degli annunci pubblicitari. Cliccando su OK, scorrendo la pagina o proseguendo la navigazione in altra maniera acconsenti all’uso dei cookie.

Per ulteriori informazioni o per revocare il consenso fai riferimento alla Privacy del sito.