🚀 go-pugleaf

"Lieven Marchand" <mal@bewoner.dma.be> wrote in message
news:m34s4n4uap.fsf@localhost.localdomain...
> "crow" <svenb@freegates.be> writes:
[knip trage methode]
>
> O(n^2) insertion sort achtig.
>
> Als je lijst gesorteerd is, is het gewoon doorlopen in O(n). Zo niet,
> sorteer via een van de klassieke methodes in O(nlogn). Dit is het
> beste wat je kan bereiken, tenzij je elementen een beperkt bereik
> hebben. In dat geval kan je het principe van bucket sort gebruiken.
>
Een hash table kun je altijd gebruiken om dubbele items eruit te filteren.
Dit is ook O(n). Ik denk alleen dat de snelheidswinst minimaal is t.o.v. een
gesorteerde tweede lijst. Ik geloof ook niet dat er een standaard hash-table
template is in C++, dus dat zou dan een hoop meer moeite zijn voor weinig
winst. Als je het over een lijst van ettelijke miljoenen items kun je erover
denken, maar ik zou voor de snel te implementeren, behoorlijk snel uit te
voeren oplossing kiezen [zoals door mij ergens anders in deze thread
beschreven].

Jaap