Esiste un elenco principale della notazione Big-O per tutto?
https://stackoverflow.com/questions/180510
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Esiste un elenco principale della notazione Big-O per tutto? Strutture di dati, algoritmi, operazioni eseguite su ciascuno, caso medio, caso peggiore, ecc.
Soluzione
Dictionary of Algorithms and Data Structures è un elenco abbastanza completo e include complessità (Big- O) nelle descrizioni degli algoritmi. Se hai bisogno di ulteriori informazioni, si troveranno in uno dei riferimenti collegati e c'è sempre Wikipedia come fallback.
Altri suggerimenti
Il Libro dei Cormen tratta di insegnarti come dimostrare ciò che è grande -O sarebbe per un determinato algoritmo, piuttosto che una memorizzazione automatica dell'algoritmo nelle sue prestazioni Big-O. Il primo è molto più prezioso del secondo e richiede un investimento da parte tua.
Prova " Introduzione agli algoritmi " di Cormen, Leisersen e Rivest. Se non è lì probabilmente non vale la pena conoscerlo.
In c ++ gli standard STL sono definiti dalle caratteristiche Big-O degli algoritmi e dai requisiti di spazio. In questo modo è possibile alternare tra implementazioni concorrenti di STL e sapere comunque che il proprio programma aveva le stesse caratteristiche di runtime. Implementazioni STL particolarmente buone potrebbero anche elenchi di casi speciali di tipi particolari per essere migliori dei requisiti standard.
Ha reso facile scegliere l'iteratore o il tipo di elenco corretti per un problema specifico, perché si poteva facilmente pesare tra consumo di spazio e velocità.
Ofcourse Big-O è solo una linea guida poiché tutte le costanti vengono rimosse. Se un algoritmo viene eseguito in k * O (n), sarebbe classificato come O (n), ma se k è sufficientemente alto potrebbe essere peggiore di O (n ^ 2) per alcuni valori di n e m.
Introduzione agli algoritmi, Seconda edizione , alias CLRS (Cormen, Leiserson, Rivest, Stein) , è la cosa più vicina a cui riesco a pensare.
Se fallisce, prova The Art of Computer Programming , di Knuth. Se non è in quelli, probabilmente devi fare qualche vera ricerca.
A chiunque arrivi a questa domanda da Google.
