Il concetto di complessità computazionale è importante per gli sviluppatori di software? [chiuso]

Nella maggior parte delle università, presumo (spero!) che la complessità del tempo e della memoria faccia decisamente parte dei loro corsi.

Ora, queste "complessità" sono un argomento molto elastico. Se le persone debbano veramente conoscere tutta la teoria del tipo "ZPP è la classe di complessità dei problemi decisionali che può essere risolta con errore zero su una macchina di Turing probabilistica in tempo polinomiale". e questo tipo di cose è discutibile. Personalmente considero queste teorie avanzate irrilevanti per lo sviluppo del software.

Al contrario, ritengo che lo sviluppatore ogni dovrebbe essere consapevole della complessità tempo / spazio delle strutture dati e degli algoritmi che usano.

Molti principianti soffrono di ossessione di micro-ottimizzazione. Comp. Di apprendimento la complessità guida gli studenti verso un modo molto più pratico di stimare le prestazioni e la scalabilità, nella mia esperienza.

Da quello che ho visto, sembra che la notazione O grande e la complessità del tempo e della memoria siano enfatizzate molto nell'educazione formale informatica ... tuttavia essendo autodidatta, questa percezione si basa sull'ascolto e la lettura di ciò che le persone con tali educations dire e scrivere.

Anche se credo che le idee e i concetti generali siano importanti, non credo che la formalizzazione di essa (come la notazione O grande e la terminologia varia) contenga quasi altrettanto, tranne che per gli scopi della comunicazione. Solo perché qualcuno non ha familiarità con la notazione formale e la terminologia non significa che non possono vedere come e perché un algoritmo sarebbe più veloce di un altro in un caso particolare. Le persone possono vedere che il tempo necessario per cercare un albero binario bilanciato si riferisce al logaritmo in base 2 del numero di nodi senza prima apprendere la teoria della complessità in alcun senso formale, se capiscono come funziona l'albero e hanno una ragionevole comprensione dell'alto matematica scolastica. È importante sapere quando prestare attenzione alla complessità e all'uso della memoria e considerare i casi tipici e peggiori, anche se ... ma alcuni non lo fanno. Ovviamente, un background formale nella teoria potrebbe aiutare, ma non averlo non significa che non si possano applicare i concetti.

La notazione e la terminologia diventano importanti per la comunicazione. Offrono un buon modo per trasmettere una quantificazione delle prestazioni di un algoritmo a qualcun altro. Dal momento che emerge spesso nei documenti e nelle spiegazioni, è utile avere almeno una vaga comprensione di esso in modo che sia più facile da seguire.

Quindi sì, i concetti sono importanti (anche se meno quando risorse e tempo sono ampi ma i dati non lo sono). Ma sebbene i concetti siano importanti, la loro formalizzazione spesso non è così importante - e bisogna ricordare che la notazione e la terminologia non sono le stesse dei concetti stessi.

Modifica

Non pretenderei di comprendere i concetti in modo così dettagliato come qualcuno che ha studiato formalmente, ma molte idee generali hanno senso. Penso che ci sia valore nello studio formale di questo, ma alcuni di quel valore possono ancora esistere senza.

Per quanto riguarda l'introduzione dei concetti (al di fuori dello studio formale), penso che un buon inizio sia incoraggiare le persone a pensare a quanta memoria in testa hanno le strutture dati, quali passaggi coinvolgono gli algoritmi e come queste cose cambiano con dati diversi.

Aiuta anche a considerare situazioni e cambiamenti ipotetici, come considerare cosa succede se un albero è bilanciato rispetto a quello che succede se è il più sbilanciato possibile, o quanti livelli nell'albero dovrebbero essere la maggior parte dei nodi, o quanti più nodi che può contenere se la profondità è aumentata di un livello. Questo modo di pensare è generalmente utile per i programmatori, non solo quando si guarda alla complessità; e se applicato a pensare a come gli algoritmi e le strutture dati si comportano in circostanze diverse, naturalmente punta nella stessa direzione di un esame più formale della complessità.

Sì

Comprendere le basi della complessità è importante e dovrebbe essere qualcosa che impari come studente. In realtà penso che di solito viene toccato in qualsiasi classe ti insegni sulle strutture dati. Riesco a capire che i laureati non capiscono o non ricordano, ma non riesco a vederli non avendo imparato le basi della complessità.

Aggiornamento: Perché è importante

Ero in una migrazione di database in un particolare lavoro. Avevamo una scadenza per quando la migrazione doveva essere completata. La persona che ha scritto la sceneggiatura non ha avuto alcun fondamento nella complessità. Sfortunatamente, nessun altro ha esaminato attentamente la logica usata nella sceneggiatura. Non ricordo le specifiche se non che usava un ciclo doppiamente annidato invece di un hashtable. Dopo una settimana in cui la sceneggiatura è stata eseguita continuamente, abbiamo preso l'aspetto della logica, compreso il problema. Ci sono volute circa 5 ore per completare dopo il cambiamento. Abbiamo quasi mancato la scadenza per il completamento della migrazione a causa di qualcuno che non capiva la complessità.

Il punto è che è facile creare accidentalmente qualcosa di più lento o che esaurirà la memoria prima del completamento del lavoro. Mentre le macchine più veloci con più memoria possono mitigare piccoli errori, spesso non possono mitigare i problemi di complessità.

Trovo che chiedere se sia "importante o no" è piuttosto vago.

Troverai molte persone che evangelizzano su come ogni minimo frammento di conoscenza in questo mondo sia strettamente richiesto a loro avviso. Ma questo è un po 'inutile, perché non si può mai sapere tutto, e non ci si dovrebbe aspettare a meno che non aiuti uno a soddisfare i requisiti posti dal suo lavoro. Preferisco adottare un approccio più pragmatico ai prerequisiti formativi, in generale, a meno che non si tratti di hobby o di preferenze personali arbitrarie.

È importante per i programmatori che dovrebbero scrivere codice estremamente efficiente o algoritmi infrastrutturali innovativi? Sì.

È importante per i programmatori che sviluppano applicazioni web convenzionali? Possono gestire senza di essa o ottenere implementazioni efficienti nel mondo open source.

È importante per i programmatori che sviluppano GUI per le applicazioni? Probabilmente no, perché i framework GUI riusciti estrapolano tutti quei piccoli dettagli.

È sempre bello sapere, proprio come qualsiasi cosa, ma non impedisce a molti (o addirittura alla maggior parte dei programmatori) di fare semplicemente il proprio lavoro con soddisfazione dei propri dipendenti.

D'altra parte, se ci si iscrive agli studi superiori, alla ricerca di un'educazione fondamentale e teorica, ci si dovrebbe aspettare che apprendano argomenti che sono per definizione più teorici che pratici. A mio parere, è essenziale che CompSci. gli studenti apprendono la complessità, così come è importante che imparino il calcolo.

Ma comunque, da quando CompSci. i programmi insegnano alle persone come essere bravi programmatori? Per questo hai programmi di formazione specializzati ed esperienza pratica (sia tu che i tuoi colleghi programmatori che possono condividerli con voi).