Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Salve a tutti.
In questo topic, come evidenzia il titolo vorrei discutere dell'algoritmo di ordinamento MergeSort.
Io personalmente lo sto analizzando in questi giorni.
L'implementazione che sto analizzando è di tipo ricorsiva e ciò che mi presenta dei dubbi è la parte di Merge degli elementi.
La versione per così dire standard fornisce una implementazione del merge che sfrutta un vettore ausiliario sul quale "fondere" in modo ordinato gli elementi del vettore originario. Nulla in contrario a questa implementazione, ma è successo che il mio prof all'università mi propone di realizzare una funzione merge che non usufruisca del vettore ausiliario. Io sono giunto alla soluzione però questo peggiora la complessità dell'algoritmo che da nlogn diviene ((n/2)^2)logn.
Il che mi pone davanti ad un dilemma : meglio preferire la memoria o la complessità. Ossia sacrificare un pò di memoria per un algoritmo più veloce, o meglio un algoritmo più lento ma con un risparmio di memoria?
Vorrei conoscere il vostro parere in merito anche perchè mi sembra un punto di discussione piuttosto interessante
[...]
Il che mi pone davanti ad un dilemma : meglio preferire la memoria o la complessità. Ossia sacrificare un pò di memoria per un algoritmo più veloce, o meglio un algoritmo più lento ma con un risparmio di memoria? [...]
Memoria o velocita'... questo e' il dilemma...
Eheh... e' il dilemma che si e' posto ogni programmatore della storia dell'informatica e non esiste una risposta unica, dipende dal caso particolare, per esempio se il vettore da ordinare e' composto da milioni di elementi (e magari ogni elemento e' un oggetto) magari e' preferibile la soluzione senza vettore ausiliario, se invece gli elementi sono meno e, per esempio, l'ordinamento fa parte di un problema piu' grosso dove le prestazioni sono importanti (per esempio l'ordinamento dei pacchetti IP in un router), magari e' preferibile la soluzione piu' veloce.
Spero di essere stato abbastanza chiaro, ora a te la scelta.
si chiarissimo grazie
La penso come te. Ritengo che nel caso dei primi computer forse era preferibile alle volte la memoria alla velocità in quanto la prima era piuttosto limitata XD ma oramai che la memoria è piuttosto elevata forse è preferibile sacrificarne un pò, salvo in casi dove la quantità di dati è talmente elevata da dover ripiegare, e preferire la memoria alla velocità.
... ma oramai che la memoria è piuttosto elevata forse è preferibile sacrificarne un pò, salvo in casi dove la quantità di dati è talmente elevata da dover ripiegare, e preferire la memoria alla velocità ...
ti consiglio comunque di analizzare caso per caso, ancora oggi ci sono casi in cui le risorse di memoria sono limitate ( per esempio lavorai a un progetto in cui si voleva far girare un client o un server su una smartcard, e il parametro piu' critico era appunto la memoria )
anche perchè mi sembra un punto di discussione piuttosto interessante 
