fra95ncy ha scritto:
...Detto questo, praticamente, per un numero sufficientemente grande di dati...
Come ti ho spiegato e dimostrato, è il "sufficientemente grande" da dover essere conosciuto, o almeno stimato
... le liste risultano avere generalmente una complessità minore per quanto riguarda alcune operazioni (per esempio l'inserimento di un elemento in coda)... ipotizzo che si debba ragionare pensando a quale operazione un ipotetico utente, userà maggiormente...Giusto?
Giustissimo.
Supponi, ad esempio, che la funzione di ricerca non sia MAI usata (perche ad esempio devi memorizzare dati bulk o un log o cose del genere).
Inoltre, se proprio vogliamo inquadrare il problema professionalmente, non è solo la complessità intesa come tempo di esecuzione da dover essere considerata, bensì anche tutte le condizioni al contorno, che son tante e richiedono conoscenze sempre più approfondite.
La prima è l'occupazione di memoria: il tradeoff tra strutture "veloci" ma grandi e "lente" ma piccole va tenuto in considerazione, soprattutto quando i dati sono davvero tanti (il che significa più della dimensione della RAM fisica del calcolatore), questo è normalissimo nell'ambito dei database (stutture indiciali compatte per poter risiedere in memoria).
Poi, sempre andando verso lo specialistico, c'è la località degli accessi e la relativa modalità. L'hardware dell'elaboratore accede ai dati in RAM tipicamente mediante strati successivi di cache (* dipende dall'architettura della CPU) e mediante sistemi (* quasi sempre presenti) di paginazione per la virtualizzazione della memoria (* sia su RAM che su filesystem che perfino su disco oggi con i settoroni da 4k).
Algoritmi apparentemente buoni (tipo hash) determinano tipicamente grande scattering nell'accesso alla RAM, quindi caricamento nella cache di pagine separate, discard dei dati interni, problemi coi TLB e così via
Algoritmi apparentemente cattivi (di elaborazione sequenziale) invece possono spesso beneficiare del pre-caricamento sia delle pagine (dal pool virtuale o fisico della memoria) sia soprattutto con la cache di primo livello, ottenendo prestazioni di gran lunga superiori.
Poi c'è tutto il discorso relativo all'implementazione, ovvero alla disponibilità per certe CPU di particolari estensioni (o istruzioni) che consentono di implementare efficientemente certi algoritmi, piuttosto che altri.
In sostanza la complessità di un algoritmo "pensato ad alto livello" non è affatto pari a quella dell'algoritmo "concretamente" eseguito dal calcolatore.