Differenza costo computazionale problema algoritmo

[Heisenberg303]

Salve a tutti,a breve dovrò sostenere l'esame di laboratorio di informatica I per la laurea in fisica. Il professore ci ha lasciato una lista di domande ipotetiche per l'orale ma di cui alcune vanno fatte per approfondimento perchè non trattate in classe. Una domanda è la seguente

Che differenza c'è fra costo computazionale di un algoritmo e costo computazionale di un problema?

Purtroppo in rete e sui libri di testo non sono riuscito a trovare una definizione soddisfacente. Potreste aiutarmi? Purtroppo il nostro corso di laboratorio 1 è stato solo di 4 crediti quindi chiaramente non ho una conoscenza cosi ampia dell'informatica se non per interessi personali e studi passati alle superiori.
Grazie in anticipo

[vict85]

Penso che il costo computazionale di un problema sia il costo computazionale minore con cui è possibile risolvere un determinato problema. Per esempio la risoluzione di un sistema lineare ha lo stesso costo computazione di una moltiplicazione matriciale (da notare che questo è un teorema e non si conosce la complessità di nessuno dei due), ma l'algoritmo di Cramer ha un costo computazionale molto più elevato e anche l'algoritmo di Gauss è non ottimale in virtù di questa uguaglianza (il prodotto matriciale può essere risolto in meno di \(O(N^3)\) operazioni).

[onlyReferee]

Ciao Heisenberg
Quoto la risposta di vict85, fermo restando che si tratta comunque anche nel mio caso di una risposta di cui sono fortemente convinto ma su cui non metto la mano sul fuoco.
Giusto per intregrare ulteriormente quanto già spiegato da vict85 con l'esempio della risoluzione di un sistema lineare, propongo anche io un altro esempio, sicuramente più vicino all'informatica.
Al momento (e questa premessa è d'obbligo) sappiamo che l'ordinamento per scambi di una sequenza finita di elementi (un array di interi per portare un esempio in termini semplici) è un problema risolvibile in un tempo $\Omega(n \log n)$ (dove $n$ è il numero di elementi da ordinare). Questo può essere inteso come costo computazionale del nostro problema in quanto al momento non vi sono algoritmi il cui tempo di esecuzione (che intendiamo pertanto come costo computazionale dell'algoritmi) sia (sempre parlando nel caso peggiore) inferiore a quello citato in precedenza. Di fatto se ci pensi bene abbiamo ad esempio l'algoritmo insertion sort che risolve tale problema in $O(n^2)$ e merge sort che invece impiega un tempo $\Theta(n \log n)$.
Riassumendo possiamo dunque dire che, con una certa approssimazione, il costo computazionale del problema è il minimo dei costi computazionali che hanno gli algoritmi che lo risolvono.
Spero di esserti stato d'aiuto nella comprensione.

[apatriarca]

@onlyReferee: Una piccola correzione. Esiste un teorema che ci dice che non è possibile fare meglio di \( n\,\log n. \) Non è solo una questione di non aver ancora trovato un algoritmo migliore. Normalmente viene visto nei corsi di algoritmi.

[onlyReferee]

Grazie della correzione, apatriarca
Andando a memoria ricordavo dell'esistenza di questo limite inferiore ma non il fatto che ci fosse anche questo teorema che afferma questa impossibilità di scendere al di sotto dello stesso nell'ordinamento per scambi.

[Heisenberg303]

Va bene,vi ringrazio penso sia corretto. Anche perchè su internet non trovo nulla e questa cosa non risulta accennata purtroppo nei libri di testo a mia disposizione. Ancora grazie

[Cronovirus]

Grazie della correzione, apatriarca
Andando a memoria ricordavo dell'esistenza di questo limite inferiore ma non il fatto che ci fosse anche questo teorema che afferma questa impossibilità di scendere al di sotto dello stesso nell'ordinamento per scambi.

Credo sia più corretto chiamarlo "ordinamento per confronto", più che "ordinamento per scambi". Ma l'importante è avere capito il concetto

[Cronovirus]

Va bene,vi ringrazio penso sia corretto. Anche perchè su internet non trovo nulla e questa cosa non risulta accennata purtroppo nei libri di testo a mia disposizione. Ancora grazie

La dimostrazione è addirittura su wikipedia https://it.wikipedia.org/wiki/Algoritmo_di_ordinamento