Complessità computazionale

di il
15 risposte

Complessità computazionale

Indicare la complessità computazionale nel caso migliore e nel caso peggiore dei seguenti algoritmi
di ordinamento: InsertionSort, SelectionSort, BubbleSort, MergeSort, QuickSort.


Ma cosa si intende con complessità computazionale?

15 Risposte

  • Re: Complessità computazionale

    Https://www.cs.unicam.it/merelli/algoritmi-complessita/Esercitazione2.pdf

    http://www-db.deis.unibo.it/courses/FIL-B/Lezioni/complessita.pdf

    http://www.diit.unict.it/users/scava/dispense/FdI_270/ComplessitaComputazionaleC.pdf

    Come è andato l'esame?
  • Re: Complessità computazionale

    oregon ha scritto:



    Come è andato l'esame?
    Grazie Oregon, adesso studio quello che e' contenuto in quei link!

    Per quanto riguarda l'esame, mi sono ritirato in quanto la scuola mi ha chiamato per mio figlio che non si stava sentendo bene, ma ho le traccie e sono esercizi fattibili, pensavo peggio!

    In questi giorni risolvero'punto per punto e possibilmente vi inviero' la mia soluzione!

    Diaciamo che mi sono tranquillizzato in quanto sono esercizi che non vanno oltre quello che il prof. ha fatto alle lezioni e come voi mi insegnate/sapete, non tutti i prof. universitari danno traccie d'esame che sono fattibili con gli argomenti trattati a lezione!
  • Re: Complessità computazionale

    Deve durare tanto questa pantomima?

    Se hai bisogno di una mano davvero comportati normalmente.
  • Re: Complessità computazionale

    Weierstrass ha scritto:


    Deve durare tanto questa pantomima?

    Se hai bisogno di una mano davvero comportati normalmente.
    Ritengo che il beneficio del dubbio vada sempre concesso, ma questo non significa che siamo così ingenui... penso che qualche domanda ce la siamo posta tutti!
    In ogni caso sono d'accordo, calcare troppo la mano sul pietismo mi sembra un approccio alquanto discutibile, a maggior ragione se le cose stanno realmente in questi termini...
  • Re: Complessità computazionale

    Weierstrass ha scritto:


    Deve durare tanto questa pantomima?

    Se hai bisogno di una mano davvero comportati normalmente.

    Scusami, ma non so il perchè di quello che dici, comunque non mi ritrovo nelle affermazioni che leggo
  • Re: Complessità computazionale

    Amico Oregon, ho finito adesso di studiare le prime slide che mi hai inviato, cioè Complessità Computazionale di un Algoritmo e proprio in quel contesto ho trovato la Complessività computazionale dell'algoritmo BubbleSort.

    In quelle slide, precisamente alla pagina 15, si da la conclusione che la complessività computazionale dell'algoritmo BubbleSort equivale ad:

    O(n^2 )

    ed equivale ad una funzione quadratica.

    Quindi deduco che il confronto con gli altri algoritmi, andrà fatto con le relative funzioni che vengono attribuite?
    Giusto?
  • Re: Complessità computazionale

    Gli altri algoritmi avranno complessità computazionali diverse secondo altre funzioni O(,,,) e li potrai confrontare per capire quale sarà il più veloce.

    Ma devi esercitarti a calcolare la complessità di un qualsiasi codice se ti verrà chiesto all'esame.
  • Re: Complessità computazionale

    Ciao Oregon, infatti oggi continuero' a studiare le altre due slide che mi hai inviato, ma dubito sul fatto il prof. vorra' i calcoli!
    Penso che vorra'una risposta intuitiva...
    Pensa che la domanda oggetto di questo thread e' proprio la domanda numero 4 dell'esame dell'altro giorno, solo che in aula, il prof. non ci ha mai spiegato questi concetti, ci ha accennato la rapidita' e non di un algoritmo, ma in tutte le slide e lezioni, non si e'mai addentrato...
    Infatti mi stupisce la domanda ma penso che voglia una risposta non molto dettagliata.

    Resta comunque che io oggi, mi concentrero' sulle slide che mi hai inviato e poi daro' la mia risposta!
  • Re: Complessità computazionale

    oregon ha scritto:


    Gli altri algoritmi avranno complessità computazionali diverse secondo altre funzioni O(,,,) e li potrai confrontare per capire quale sarà il più veloce.

    Ma devi esercitarti a calcolare la complessità di un qualsiasi codice se ti verrà chiesto all'esame.
    Ho contattato il Prof. e gli ho chiesto come facevo a rispondere alla domanda sulla complessità computazionale?
    Mi ha detto che non dovevo analizzare la complessità computazionale della funzione, in quanto quello è un esercizio per coloro che hanno esame con 7 CFU e più, infatto vi è esercizio 7 che adesso posterò, che li si si richiede il calcolo della complessità, che per me non è previsto!

    Quello che vedete non è per il mio corso da 6CFU
    Allegati:
    31893_16d145e2c0fbf065a0a3d0bf8e5bea24.jpg
    31893_16d145e2c0fbf065a0a3d0bf8e5bea24.jpg
  • Re: Complessità computazionale

    Allora adesso mi chiedo, se l'esercizio che è il seguente:

    Indicare la complessità computazionale nel caso migliore e nel caso peggiore dei seguenti algoritmi
    di ordinamento: InsertionSort, SelectionSort, BubbleSort, MergeSort, QuickSort.


    A cui dovrei rispondere io, e considerando che il prof. mi ha risposto che questo esercizio è inierente ad algoritmi di ordinamento e che quindi devo rispondere in quanto fa parte del mio corso da 6CFU, allora, come devo rispondere?

    Perchè chiedo come devo rispondere?
    Per il semplice motivo che sto studiando le slide che mi avete inviato e mi sembra che siano più inierenti al corso da 7CFU, cioè non il mio da 6CFU, quindi adesso ho dei dubbi su quale risposta si dovrebbe dare all'esercizio di mio interesse?
  • Re: Complessità computazionale

    Non ci sto capendo nulla.

    Ti ho mandato quelle slide perché tu hai fatto la domanda sulla complessità all'inizio del thread.

    Se il professore ti ha detto che non dovrai rispondere a queste domande, semplicemente ignora tutto.
  • Re: Complessità computazionale

    Se hai il programma ridotto, puoi studiarti i risultati generali senza entrare nel dettaglio. È come sapere il risultato di un teorema senza sapere la dimostrazione.
    Per la domanda che ti ha fatto puoi anche fare riferimento alla tabella di Wikipedia (prime tre colonne di sinistra)
    https://en.m.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

    Riordina le idee su quello che è davvero il tuo programma, come ti ha suggerito Oregon. Sicuramente il professore ti avrà fornito dispense o altro per il programma ridotto
  • Re: Complessità computazionale

    Quindi la questione e' semplice:

    1) nel corso da 6cfu, sono stati spiegati gli algo di ordinamento ed e' stata indicata la loro complessita' computazionale (CC)
    2) nel corso da 7cfu viene spiegato anche COME si calcola, in generale.

    Per gli algo di ordinamento, LO SI SA GIA': sono gia' stati analizzati ere geologiche fa. E la loro CC non cambia nel tempo!
  • Re: Complessità computazionale

    Weierstrass ha scritto:




    Riordina le idee su quello che è davvero il tuo programma, come ti ha suggerito Oregon. Sicuramente il professore ti avrà fornito dispense o altro per il programma ridotto
    Si, lo sto facendo, il fatto che al prof. c'è da chiedere e attendersi delle risposte, in quanto fa questo corso a 300 persone e ci sono un mix di 9 CFU, 7 CFU e poi quelli a scelta da 6 CFU, e il prof. fa fatica e quindi ho dovuto contattarlo più volte per capire quali slide dovevo eliminare e non.
    Poi essendo un esame che è presente a Lecce, mentre io sono alla succursale a Brindisi, ogni volta per andare è un casino e quando lo si contatta da remoto non è come andare a ricevimento...
    Diciamo che con la prova d'esame che ho adesso, sto riuscendo a capire quello che devo o non devo fare, andando a chiedere ogni volta!
    Le slide che ho le so a memoria, ma occorre integrare, anche per i programmi da fare!

    Per il resto vi ringrazio per le dritte che mi state dando, io non sono un informatico, sono specializzato nel settore metalmeccanico e in particolare nell'Aerospazio.

    Ma devo fare bene con questo esame e quindi devo lavoraci su!
Devi accedere o registrarti per scrivere nel forum
15 risposte