Sitter och håller på med en grej där jag ska ta bort lite dubletter (och tripletter, etc.) ur en osorterad vektor. Den första ska behållas, alla andra ska bort.

Kollade lite på vad någon annan skrivit för gammal kod, och eftersom det är relativt lite data, körde jag på samma ide; "för alla element1, kolla alla element2, om element2=element1 och element1 inte är element2, ta bort element2".
Alltså en O(n^2)-algoritm.

Jag kom dock på att det finns (åtminstone) en O(nlogn)-algoritm som funkar, tyvärr lite tråkig. Någon som kan komma på eller vet om det finns någon O(nlogn)-algoritm för ändamålet?

Jag är inte så vass på matematik men programmeringsmässigt hade jag väl löst detta genom att sortera vektorn och sedan flytta över till vektor2 när värdet förändras i vektor1 så att bara unika värden kopieras. Det blir ju rätt snabbt då bara ett genomlöp krävs. Det är väl det du var ute efter? :)

<b>Någon som kan komma på eller vet om det finns någon O(nlogn)-algoritm för ändamålet?</b>
Kan du förklar på bönders språk hur detta funkar ungefär.

Jag lade upp ett program för några år sedan i Vb som löser det
men du vill förmodligen ha något vassare

Programarkivet:Ta Bort Dubbletter

Använder man quicksort i Olas förslag får man komplexiteten O(n log n) + O(n) = O(n log n).

Du berättade inte om du vill att ordningen skall vara oförändrad.

Med en bra hashfunktion borde dock O(N) vara möjligt.

<b>>Jag är inte så vass på matematik men programmeringsmässigt hade jag väl löst detta genom att sortera vektorn och sedan flytta över till vektor2 när värdet förändras i vektor1 så att bara unika värden kopieras. Det blir ju rätt snabbt då bara ett genomlöp krävs. Det är väl det du var ute efter? :) </b>
Det är i stort sett så jag gjorde det.

<b>>Använder man quicksort i Olas förslag får man komplexiteten O(n log n) + O(n) = O(n log n).</b>
Exakt det jag gjorde. Fast quicksort är väl bara nlogn i average case tror jag... ?
Skit samma, det finns nlogn-sök-algoritmer, och då får man det. Tänkte om någon kände till någon annan metod

<b>>Du berättade inte om du vill att ordningen skall vara oförändrad. </b>
Det avsåg jag. Men det spelar ingen större roll. Det är bara att sortera tillbaka på ursprunglig ordning, komplexiteten ändras inte.

<b>>Med en bra hashfunktion borde dock O(N) vara möjligt. </b>
Tro fan det!
Eller snarare O(max(N,M)) där M är hashtabellens storlek?


<b>>Kan du förklar på bönders språk hur detta funkar ungefär.</b>
Låt säga att du sorterar en vektor med n element med en vanlig variant av bubblesort; då gör du något i stil med (i C-style):
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
Gör val på i och j, swappa.

eller i VB-style:

for i=0 to n
for j=0 to n
Gör val på i och j, swappa.
next j
next i

För varje förändring i "i" gör du n förändringar i "j". totalt n*n steg, eller O(n^2).
Skulle du ha en algoritm som funkar som en original bubbelsort hade du fått

for(int i=0; i<n; i++)
for(int j=i; j<n; j++)
Gör val på i och j, swappa.

resp

for i=0 to n
for j=i to n
Gör val på i och j, swappa.
next j
next i

Du får du inte längre n steg på varje utan n steg för i=0, n-1 för i=1, osv. Totalt blir det väl något i stil med n^2/2; lite mindre än n^2 i alla fall. Vi kallar ändå det för O(n^2). Det är så att säga "inte väsentligt bättre".

Det finns exakta matematiska definitioner för det. O-notationen beskriver hur (t.ex.) en algoritm beter sig vid stora problem; hur mycket värre lösningen blir när vi gör problemet lite värre.