{"id":2136,"date":"-0001-11-30T00:00:00","date_gmt":"-0001-11-29T23:10:04","guid":{"rendered":""},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T22:00:00","slug":"2136","status":"publish","type":"post","link":"https:\/\/www.vialattea.net\/content\/2136\/","title":{"rendered":"A scrivere siamo degli studenti di un corso di Fondamenti di Informatica II e gradiremmo alcuni chiarimenti circa la teoria della complessit\u00e0 computazionale, che ha sollevato in noi parecchi dubbi e fraintendimenti:\r\n\r\n1) Per “complessit\u00e0 computazionale” si deve intendere\r\nuna “stima del numero di operazioni” che compongono un\r\nalgoritmo e\/o una “scienza che studia i criteri” di\r\nefficienza degli algoritmi?\r\n\r\n2) Se per “complessit\u00e0 computazionale” si accetta la\r\nseconda accezione, \u00e8 possibile parlare di “complessit\u00e0\r\ncomputazionale temporale” e “complessit\u00e0\r\ncomputazionale spaziale” come finalizzate\r\nall\u2019ottimizzazione di risorse rispettivamente\r\ntemporali e spaziali, oppure \u00e8 esatto parlare di\r\ncomplessit\u00e0 computazionale se riferita alla\r\nvalutazione del tempo e complessit\u00e0 spaziale quando\r\nriferita alla memoria ?\r\n\r\n3) Sono convinto di non aver ben capito a fondo quali\r\nsono le regole pratiche per il calcolo della\r\ncomplessit\u00e0 di un algoritmo e perch\u00e9 sono tali.\r\nAd esempio, un ciclo “for (int i=1; iLa
\n complessit\u00e0 computazionale di un algoritmo \u00e8 definita come l’ordine di
\n grandezza della funzione che determina il numero di passi elementari da
\n svolgere per eseguirlo, al crescere della dimensione dei dati di ingresso.<\/font><\/p>\n

La complessit\u00e0 computazionale<\/i>,
\n in questo senso, \u00e8 quindi una misura di tempo astratta che ha,
\n al pi\u00f9, una relazione di proporzionalit\u00e0 con il tempo
\n effettivo di esecuzione<\/i>.<\/font><\/p>\n

Si parla anche di complessit\u00e0
\n computazionale spaziale, intesa come dimensione della struttura dati necessaria
\n a supportare l\u2019esecuzione di un algoritmo. Tuttavia, non si dovrebbe associare
\n la complessit\u00e0 (computazionale) spaziale alla memoria e computazionale
\n al tempo, poich\u00e9 in entrambi i casi si sta valutando l\u2019ordine
\n di grandezza<\/i> delle quantit\u00e0 associate (tempo e memoria).<\/font><\/p>\n

L\u2019analisi della complessit\u00e0
\n temporale di un algoritmo consente di determinare l\u2019ordine di grandezza
\n del tempo necessario per eseguirlo senza nemmeno iniziare la computazione.
\n Questo approccio ha dei vantaggi considerevoli, infatti \u00e8 possibile
\n scrivere algoritmi che terminano in un numero considerevole di anni.<\/font><\/p>\n

Si supponga di scrivere il seguente
\n algoritmo ricorsivo per il calcolo del fattoriale:<\/font><\/p>\n

Algoritmo F1<\/b>:<\/font><\/p>\n

if n = 0 then <\/font><\/i><\/p>\n

\n

f = 1;<\/font><\/i><\/p>\n<\/blockquote>\n

else<\/font><\/i><\/p>\n

\n

\tf = n*F1(n-1);<\/font><\/i><\/p>\n<\/blockquote>\n

e si supponga di voler calcolare
\n F1(1000)<\/i> con un calcolatore in grado di fare un miliardo di iterazioni
\n elementari (o passi<\/i>) al secondo: occorrerebbero 2551 anni.<\/font><\/p>\n

L\u2019analisi della complessit\u00e0
\n dell\u2019algoritmo F1 consente, quindi, di non dover attendere il risultato
\n fino al capodanno del 4550.<\/font><\/p>\n

Le regole di valutazione della complessit\u00e0
\n computazionale sono le seguenti:<\/font><\/p>\n

    \n
  • Le istruzioni di assegnamento
    \n hanno complessit\u00e0 unitaria. <\/font><\/li>\n
  • Le iterazioni di tipo for
    \n i = 1 to n do c<\/i> hanno complessit\u00e0 n<\/i> volte la complessit\u00e0
    \n del corpo dell\u2019iterazione c<\/i>. <\/font><\/li>\n
  • Se un algoritmo contiene istruzioni
    \n condizionali di tipo if \u2026 then \u2026 else<\/i>, allora ha complessit\u00e0
    \n minima, media <\/i>e massima<\/i> pari al numero di passi minimo<\/i>,
    \n medio<\/i> e massimo<\/i> necessari allo svolgimento delle istruzioni
    \n condizionali che lo compongono.<\/font><\/li>\n<\/ul>\n

    Con queste regole siamo in grado
    \n di valutare la complessit\u00e0 computazionale di un algoritmo al crescere
    \n della dimensione dei dati di ingresso.<\/font><\/p>\n

    Si consideri ora l\u2019algoritmo per
    \n il calcolo del fattoriale che segue:<\/font><\/p>\n

    Algoritmo F2<\/b>:<\/font><\/p>\n

    f = 1;<\/font><\/i><\/p>\n

    if n > 1 then<\/font><\/i><\/p>\n

    \n

    for i = 1 to n do f = f * i;<\/font><\/i><\/p>\n<\/blockquote>\n

    Ora, applicando le regole di calcolo
    \n della complessit\u00e0 computazionale esposte, si valuti la complessit\u00e0
    \n degli algoritmi F1 ed F2. <\/font><\/p>\n

    Si scopre che F1 ed F2 impiegano
    \n rispettivamente n!<\/i> e n+1 <\/i>passi. Il calcolatore di cui sopra
    \n eseguirebbe, quindi, F2(1000)<\/i> in un milionesimo di secondo circa.
    \n L\u2019analisi della complessit\u00e0 rivela che l\u2019algoritmo F2 \u00e8
    \n nettamente pi\u00f9 efficiente di F1.<\/font><\/p>\n

    Ma, ai fini della valutazione dell\u2019efficienza,
    \n ci\u00f2 che interessa \u00e8 l\u2019ordine di grandezza delle funzioni
    \n che determinano il numero di passi al crescere di n<\/i> o, in termini
    \n formali, l\u2019ordine di infinito<\/i> di queste funzioni.<\/font><\/p>\n

    Ricordiamo che una funzione ha lo
    \n stesso ordine di infinito xn<\/sup><\/i> se e solo se \"\"\/,
    \n per c > 0<\/i> constante. Questa propriet\u00e0 si indica affermando
    \n che “f(x) <\/i>\u00e8 O(xn<\/sup>)<\/i>“<\/font><\/p>\n

    Valutando l\u2019ordine di infinito delle
    \n funzioni che determinano il numero di passi necessari a svolgere un algoritmo
    \n siamo in grado di determinare due cose:<\/font><\/p>\n

      \n
    1. un criterio di efficienza degli
      \n algoritmi<\/font><\/li>\n
    2. delle classi di computabilit\u00e0
      \n di algoritmi<\/font><\/li>\n<\/ol>\n

      Siano f1(n) <\/i>ed f2(n)<\/i>
      \n due funzioni di valutazione di complessit\u00e0 computazionale relativi
      \n agli algoritmi A<\/i> e B<\/i> rispettivamente. <\/font><\/p>\n

        \n
      1. A <\/i>e B <\/i>hanno la
        \n stessa efficienza: \"\"\/,
        \n con c > 0 <\/i>constante.<\/font><\/li>\n
      2. A <\/i>\u00e8 pi\u00f9
        \n efficiente di B<\/i>: \"\"\/<\/font><\/li>\n
      3. B <\/i>\u00e8 pi\u00f9
        \n efficiente di A<\/i>: \"\"\/<\/font><\/li>\n<\/ol>\n

        Le classi di computabilit\u00e0
        \n degli algoritmi vengono invece definite sulla gerarchia di ordini di infinito
        \n delle funzioni di valutazione della complessit\u00e0 computazionale:<\/font><\/p>\n

          \n
        • Complessit\u00e0 polinomiale:
          \n algoritmi O(ni<\/sup>) <\/i>per qualche i <\/i><\/font><\/li>\n
        • Complessit\u00e0 esponenziale:
          \n algoritmi O(an<\/sup>) <\/i>per qualche a <\/i><\/font><\/li>\n
        • Complessit\u00e0 non-polinomiale:
          \n tutti gli altri algoritmi<\/font><\/li>\n<\/ul>\n

          L\u2019algoritmo F1 \u00e8 quindi O(n!)
          \n <\/i>(non-polinomiale), ment<\/font><\/p>\n","protected":false},"excerpt":{"rendered":"

          […]<\/p>\n","protected":false},"author":180,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[62],"tags":[],"class_list":["post-2136","post","type-post","status-publish","format-standard","hentry","category-software"],"_links":{"self":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/2136","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/users\/180"}],"replies":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/comments?post=2136"}],"version-history":[{"count":0,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/2136\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/media?parent=2136"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/categories?post=2136"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/tags?post=2136"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}