Complessità algoritmi

[Mr.Paschi!]

C'è un software che dato un algoritmo me ne ricavi la complessità( O(1) logn ecc..ecc..)?
Opero in Java (quindi anche se lo facesse JBuilder o Eclipse andrebbe bene)

[Ziosilvio]

Non vorrei sbagliare, ma credo che la risposta sia negativa.

[Mixmar]

Originariamente inviato da Ziosilvio

Non vorrei sbagliare, ma credo che la risposta sia negativa.

Non solo penso che non esista, ma credo che non possa esistere (è per quello che hai grassettato il termine "negativa", vero Ziosilvio? ).

[dnarod]

un algoritmo non banale fa sicuramente qualcosa di non prevedibile "su carta".....cioe, bisogna pensare al caso peggiore, ma non penso (in realta pero non ci sto pensando molto, un modo per cui potrebbe anche esserci) ci sia qualcosa del genere, è abbastanza difficile realizzare una cosa che vada bene sempre....direi di no cosi su due piedi, ma potrei sbagliare...

[cdimauro]

Non può esistere un algoritmo del genere. Se esistesse, vorrebbe dire che di qualunque software sarebbe possibile fornire un'analisi precisa, che potrebbe servire anche a scoprire eventuali bug (e quindi il classico problema dell'arresto). Impossibile.

[Ziosilvio]

Originariamente inviato da Mixmar

Non solo penso che non esista, ma credo che non possa esistere (è per quello che hai grassettato il termine "negativa", vero Ziosilvio? ).

Esattamente.
E la dimostrazione proposta da cdimauro mi sembra andar bene.

[cj++]

Originariamente inviato da cdimauro

Non può esistere un algoritmo del genere. Se esistesse, vorrebbe dire che di qualunque software sarebbe possibile fornire un'analisi precisa, che potrebbe servire anche a scoprire eventuali bug (e quindi il classico problema dell'arresto). Impossibile.

Scusami ma nn mi è chiaro il legame fra bug e complessità asintotica.

Tra l'altro la complessità asintotica non è di un software ma di un singolo algoritmo. Ed anche nel caso in cui la sua complessità sia penosa se ne risente in termni di tempo e di risorse ...nn è certo qualcosa per cui serva un debugger (nn ci sono errori sintattici/semantici, ma solo di implementazione).


Inoltre, nn so se abbiate fatto Algoritmi all'uni ma generalmente c'è una (o piu) sommatoria e due righe di calcolo...

[cdimauro]

E' dall'analisi di un algoritmo che si dovrebbe poter risalire alla sua complessità in termini di spazio / tempo.

Proprio perché hai fatto Algoritmi (ai miei tempi era Sistemi), dovresti sapere che esistono soltanto alcuni metodi che ti permettono di risalire, ALCUNE VOLTE, alla complessità di un algoritmo. In generale, dato un QUALUNQUE algoritmo, non è possibile farlo.

Lo stesso vale per i bug: esistono degli strumenti di test e di analisi formale che permettono di determinare l'assenza o meno di bug, in particolari casi. Ma in generale, dato un QUALUNQUE algoritmo, non è possibile farlo.

In entrambi i casi mancano degli strumenti di analisi che permettono di risolvere SEMPRE E COMUNQUE i rispettivi problemi (calcolo della complessità spazio/temporale e assenza di bug del codice).
In soldoni: non è possibile costruire nessun software (e quindi "automatizzare" il procedimento. Ergo avere un procedimento formale e rigoroso) che, datogli in pasto un QUALUNQUE sorgente, riesca a portare a termine l'uno o l'altro compito.

[Mr.Paschi!]

Originariamente inviato da cj++

Inoltre, nn so se abbiate fatto Algoritmi all'uni ma generalmente c'è una (o piu) sommatoria e due righe di calcolo...

Ecco si, a volte è capitato che mi si assegnavano compiti del tipo: "creare un algortmo che faccia l'operazione X ed analizzarne la complessità"

Se posso analizzarlo io l'algoritmo, perchè non può farlo un software?
Voi dite che è possibile farlo per alcuni specifici algoritmi (tipo ordinamento, ricerche..ecc..) e non per qualsiasi?

[Ziosilvio]

Originariamente inviato da Mr.Paschi!

Se posso analizzarlo io l'algoritmo, perchè non può farlo un software?

Perché l'analisi che ne fai tu non è una computazione, ma una stima asintotica.
E anche perché non sempre tale stima è possibile o significativa.