Elements distinkthetsproblem

I beräkningskomplexitetsteori är elementets distinkthetsproblem eller elementets unikhetsproblem problemet med att avgöra om alla element i en lista är distinkta.

Det är ett väl studerat problem i många olika beräkningsmodeller. Problemet kan lösas genom att sortera listan och sedan kontrollera om det finns några på varandra följande lika element; det kan också lösas i linjär förväntad tid med en randomiserad algoritm som infogar varje objekt i en hashtabell och jämför endast de element som är placerade i samma hashtabellcell.

Flera nedre gränser i beräkningskomplexitet bevisas genom att reducera elementdistinkthetsproblemet till problemet i fråga, dvs genom att visa att lösningen av elementunikhetsproblemet snabbt kan hittas efter att problemet i fråga har lösts.

Beslutsträdets komplexitet

Antalet jämförelser som behövs för att lösa problemet med storlek $n$ , i en jämförelsebaserad beräkningsmodell som ett beslutsträd eller ett algebraiskt beslutsträd , är $\Theta ( n\log n)$ . Här anropar $\Theta$ big theta notation , vilket betyder att problemet kan lösas i ett antal jämförelser proportionellt mot $n\log n$ (en linjärtmisk funktion ) och att alla lösningar kräver så många jämförelser. I dessa beräkningsmodeller kan inmatningsnumren inte användas för att indexera datorns minne (som i hashtabelllösningen) utan kan endast nås genom att beräkna och jämföra enkla algebraiska funktioner av deras värden. För dessa modeller löser en algoritm baserad på jämförelsesort problemet inom en konstant faktor av bästa möjliga antal jämförelser. Samma nedre gräns gäller också för det förväntade antalet jämförelser i den randomiserade algebraiska beslutsträdsmodellen .

Kvantkomplexitet

Kvantalgoritmer kan lösa detta problem snabbare, i ${\textstyle \Theta (n^{2/3})}$ frågor. Den optimala algoritmen är av Andris Ambainis . Yaoyun Shi visade först en snäv nedre gräns när storleken på intervallet är tillräckligt stort. Ambainis och Kutin utökade oberoende (och via olika bevis) sitt arbete för att erhålla den nedre gränsen för alla funktioner.

Generalisering: Hitta upprepade element

Huvudartikel: Misra–Gries heavy hitters-algoritm

Element som förekommer mer än $n/k$ gånger i en multiuppsättning av storlek $n$ kan hittas av en jämförelsebaserad algoritm, Misra–Gries heavy hitters-algoritmen , i tiden $O(n\log k)$ . Elementets distinkthetsproblem är ett specialfall av detta problem där $k=n$ . Denna tid är optimal under beslutsträdsmodellen för beräkning.

Se även

• Kollisionsproblem