Problem z odrębnością elementów

W teorii złożoności obliczeniowej problem odrębności elementu lub problem unikalności elementu to problem określenia, czy wszystkie elementy listy są różne.

Jest to dobrze zbadany problem w wielu różnych modelach obliczeniowych. Problem można rozwiązać, sortując listę, a następnie sprawdzając, czy występują kolejne równe elementy; można go również rozwiązać w liniowym oczekiwanym czasie za pomocą losowego algorytmu , który wstawia każdy element do tablicy mieszającej i porównuje tylko te elementy, które są umieszczone w tej samej komórce tabeli mieszającej.

Kilka dolnych granic złożoności obliczeniowej jest udowodnionych przez sprowadzenie problemu wyrazistości elementu do rozpatrywanego problemu, tj. poprzez wykazanie, że rozwiązanie problemu jednoznaczności elementu można szybko znaleźć po rozwiązaniu rozpatrywanego problemu.

Złożoność drzewa decyzyjnego

Liczba porównań potrzebnych do rozwiązania problemu rozmiaru $)$ modelu obliczeniowym opartym na porównaniach, takim jak ${\ Displaystyle \ Theta ( n\log n)}$ decyzyjne lub algebraiczne drzewo decyzyjne , wynosi . Tutaj przywołuje notację big theta $,$ co oznacza, że ​​​​problem można rozwiązać za pomocą szeregu porównań proporcjonalnych do ${\ Displaystyle n \ log n}$ ( funkcja liniowo-arytmiczna ) i że wszystkie rozwiązania wymagają Θ {\ displaystyle \ Theta tyle porównań W tych modelach obliczeń liczby wejściowe nie mogą być używane do indeksowania pamięci komputera (jak w rozwiązaniu z tablicą mieszającą), ale można uzyskać do nich dostęp jedynie poprzez obliczenie i porównanie prostych funkcji algebraicznych ich wartości. W przypadku tych modeli algorytm oparty na sortowaniu porównawczym rozwiązuje problem ze stałym współczynnikiem najlepszej możliwej liczby porównań. Ta sama dolna granica dotyczy również oczekiwanej liczby porównań w modelu losowego algebraicznego drzewa decyzyjnego .

Złożoność kwantowa

$_$ kwantowe rozwiązać w Optymalny algorytm jest autorstwa Andrisa Ambainisa . Yaoyun Shi po raz pierwszy udowodnił, że dolna granica jest wąska, gdy zakres jest wystarczająco duży. Ambainis i Kutin niezależnie (i za pomocą różnych dowodów) rozszerzyli jego pracę, aby uzyskać dolną granicę dla wszystkich funkcji.

Uogólnienie: znajdowanie powtarzających się elementów

Główny artykuł: Algorytm ciężkich uderzeń Misry – Griesa

Elementy, które występują więcej niż $,$ w zbiorze wielokrotnym o rozmiarze $algorytmu$ pomocą algorytmu opartego na porównaniach, ciężkich uderzeń Misry – Griesa , w czasie ${\ Displaystyle O (n \ log k)}$ . Problem odrębności elementów jest szczególnym przypadkiem tego problemu, w którym ${\ displaystyle k = n}$ . Ten czas jest optymalny w ramach modelu obliczeniowego drzewa decyzyjnego.

Zobacz też

• Problem z kolizją