Complessità computazionale

Question

Il corso rispetto all'anno scorso è migliorato tanto per quanto riguarda gli homework, una cosa che però secondo me manca è una piccola introduzione o comunque delle nozioni di base sul costo computazionale degli algoritmi. Siccome gli homework si basano praticamente su quello e la maggior parte di chi segue il corso  non sa quanto costano le istruzioni al livello di tempo, non sarebbe interessante portarlo come argomento a lezione? Parlo ovviamente per entrambi i canali, magari anche in laboratorio. La mia è solo un idea, magari è anche già in piano per quest'anno, ma io non avrei modo di saperlo. Qualcuno la pensa come me?

Answer 1

io                              .

Comments

meno male ahahahhaah

Answer 2

Credo che parte della programmazione risieda proprio in ciò.
Oltre ad esserci vari comandi che permettono di farsi un'idea della velocità del codice, anche nelle singole parti ( https://q2a.di.uniroma1.it/13056/avviso-software-installare-anaconda-librerie-comandi-utili?course=advices/fondamenti-di-programmazione-19-20 ), gli Homework sono fatti apposta per costringerci a "pensare".
Possiamo prendere la via semplice e riempire di If e di For, ma poi il codice è lento.
A quel punto entra in gioco ciò di cui ha bisogno un programmatore: la logica (oltre a StackOverflow, ovviamente).
Al posto di mettere 2 For, potrebbe esserci un modo che ci permette di usarne uno solo, o addirittura nessuno.
Questa è anche parte del motivo per cui negli esercizi per casa è presente la richiesta di fare gli esercizi in diverse varianti (con e senza range, for, while).
Ovviamente ci possono essere anche algoritmi già pronti o formule matematiche che generalizzano interi problemi, ma questa è più questione di esperienza.
Sicuramente la tua non è una pessima idea, ma il problema è come fare una lezione del genere.
Sia in laboratorio che a lezione vengono continuamente fatte prove con %timeit per mostrare la velocità delle diverse implementazioni, quindi se potessi essere leggermente più specifico non sarebbe male :)

Answer 3

Il fatto è che a lezione viene quasi sempre considerata la questione 'tempo' di un algoritmo di una singola operazione. Infatti molte volte ci hanno ripetuto in base a cosa alcuni, per esempio, strutture dati sono migliori di altre. Faccio un esempio, per vedere se un elemento è presente la cosa migliore e lavorarci con un set. Ma facendo diverse prove, dato che il dato in input era dato in una lista, toccava andare a vedere anche il costo nel andarlo a trasformare in un set, che però era superiore rispetto a lavorare direttamente su una lista. Quello che ti voglio dire è che si, la penso come te, però fino ad un certo punto poichè il costo computazionale di un algoritmo dipende sempre da come lo vuoi strutturare tu, da quello che ti viene in mente. E non penso che i professori ti possono mettere sempre nella testa il modo piu efficace per svolgere l'algoritmo. Se no questo corso sarebbe un po una bagianata