analiza czasu algorytmu „wielkość wejściowa” a „elementy wejściowe”

Nadal jestem trochę mylony z terminami „długość wejściowa” i „rozmiar wejściowy”, gdy są używane do analizy i opisu bezobjawowej górnej granicy algorytmu

Wydaje się, że długość wejściowa dla algorytmu zależy od rodzaju danych i algorytmu, o którym mówisz.

Niektórzy autorzy odnoszą się do długości wejściowej do rozmiaru znaków, które są wymagane do reprezentowania danych wejściowych, więc „abcde”, jeśli zostanie użyte jako zestaw wejściowy w algorytmie, będzie miało „długość wejściową” wynoszącą 6 znaków.

Jeśli zamiast znaków mamy liczbę (na przykład liczby całkowite), czasami zamiast znaków używana jest reprezentacja binarna, więc „długość wejściowa” jest obliczana jako (jako L jest liczbą Max w zestawie wejściowym). $N*log(L)$

Istnieją inne problemy, które nawet jeśli zestawem wejściowym są liczby, opisują one „długość wejściową” jako „zmienne decyzyjne”, więc dla zestawu wejściowego o długości N z liczbami w zakresie długość wejściowa wynosi tylko N (na przykład suma podzbioru), lub nawet bardziej skomplikować liczbę miejsc binarnych potrzebnych do stwierdzenia problemu (to, co uważam, jest takie samo jak ) $0-2^{32}$ $N*log(L)$

Więc:

to zależy od algorytmu?
Co oznacza i kiedy używać każdej „długości” wejściowej długości
Czy jest jakaś zasada, której mogę użyć, aby zdecydować, której użyć?

— Jesus Salas
źródło

Odpowiedzi:

W najbardziej formalnym sensie wielkość danych wejściowych mierzona jest w odniesieniu do implementacji algorytmu maszyny Turinga i jest to liczba symboli alfabetu potrzebnych do zakodowania danych wejściowych.

Jest to oczywiście raczej abstrakcyjne i bardzo trudne do pracy w praktyce, a przynajmniej bardzo denerwujące - musielibyśmy zastanowić się, w jaki sposób określamy ograniczniki itp. Itd. To, co zwykle dzieje się w praktyce, to szukanie proxy pomiar wielkości wejściowych - coś bardziej wygodne i dostępne, ale to nie powoduje żadnych problemów matematycznych w naszej analizie.

Korzystając z przykładu „abcde”, zwykle jest tak, że alfabet, którego używamy do wprowadzania danych, jest niewielki, więc nawet używając pomiaru proxy znaków, wiemy, że nawet na maszynie Turinga możemy, jeśli będziemy się tym przejmować, podaj kodowanie wejściowe, które przekształciłoby „abcde” w jakąś zakodowaną formę, która miała długość co najwyżej dla niektórych stałych . To rozszerzenie o stałą zwykle nie robi różnicy w naszej analizie asymptotycznej, ponieważ rutynowo odrzucamy czynniki stałe. $5$ $5\times c$ $c$

W innym przypadku często mierzymy rozmiar wykresu wejściowego na podstawie liczby wierzchołków . Oczywiście, jeśli chcemy określić dowolnie duże wykresy, rozmiar zakodowanego wejścia nie jest po prostu - co się stało na przykład z krawędziami? Wiemy, że możemy zastosować rozsądny schemat kodowania, który reprezentuje wykres w bitach. Jest to trochę bardziej rozwinięcie niż stałe, ale w wielu interesujących przypadkach mamy do czynienia tylko z ziarnistością wielomianów, a wielomiani ładnie komponują się na wiele sposobów - w szczególności na przykład, jeśli ustalamy, że naszym czasem działania jest gdzie jest wielomianem, to wiemy, że jest jakiś wielomian $n$ $n$ $N = c\cdot n^{2}\log n$ $O(p(n))$ $p$ $p'$ takie, że , więc kiedy wrócimy do formalnej miary danych wejściowych, nadal znajdujemy się w czasie wielomianowym. $O(p(n)) = O(p'(N))$

Miejsce, w którym może to spaść, dotyczy pracy z liczbami. Ponieważ liczba o wielkości może być zakodowana w bitach , gdyby nasz czas działania wynosił , byłby to - wykładniczy w rzeczywistym rozmiarze wejściowym - który sprawiłoby, że wielkość byłaby złym wyborem dla proxy dla wielkości wejściowej, gdybyśmy chcieli na przykład porozmawiać o członkostwie w na przykład w przypadku Strong- -complete i Weakly- -kompletne, pamiętaj o tym). Z drugiej strony, gdyby wszystkim, co nas interesowało, była rozstrzygalność, byłby to wystarczająco dobry miernik zastępczy. $m$ $n = O(\log m)$ $O(m)$ $O(2^{n})$ $m$ $\mathcal{P}$ $\mathcal{NP}$ $\mathcal{NP}$

Tak więc, chociaż nie ma określonej reguły wybierania miary proxy dla rozmiaru wejściowego, wymaganie jest takie, aby rozszerzenie lub zmniejszenie rozmiaru proxy w porównaniu z wielkością wejściową były zgodne z tym, co próbujesz udowodnić. Zasadniczo stałe zmiany czynników prawie nigdy nie mają znaczenia, małe czynniki wielomianowe są zwykle w porządku i działają w przypadku większości podstawowej teorii, którą widzisz, duże czynniki wielomianowe mogą nadal działać w teorii, ale mogą być przykrą niespodzianką w praktyce, a wykładnicze wielkości zmian są zwykle zbyt ekstremalne.

— Luke Mathieson
źródło

Dziękuję za odpowiedź. Naprawdę interesująca część, o której mówisz, o wyborze odpowiedniego pełnomocnika do rozmowy o członkostwie w P lub NP dla danych wejściowych, może to być zupełnie nowe pytanie! Poza tym i wracając do poprzedniego pytania. Który według ciebie byłby wtedy najlepszym proxy dla algorytmu, którego wejściem jest zestaw liczb całkowitych? Chyba może to zależeć od algorytmu? Widzę 3 potencjalne opcje: N (długość zestawu) N * Log (L) (L jest wartością maksymalną) i Log (suma (zestaw)).

— Jesus Salas,

@JesusSalas, na pewno może zależeć od tego, co z nimi zrobisz, ale byłby najprostszą odpowiedzią „wystarczająco blisko kodowania TM”, ale nadal interesujące może być spojrzenie na czas działania pod kątem , a może i wielkość największej liczby - oczywiście jest to tylko , ale czasami łatwiej jest analizować rzeczy za pomocą nieoczywistych miar.

N \log L

$N\log L$

N

$N$

N

$N$

2^{\log L}

$2^{\log L}$

— Luke Mathieson,

Obejmuje to podstawy, ale są pewne nieścisłości. Reprezentowanie „abcde” na maszynie Turinga nie wymaga znaków: zajmuje pięć znaków, jeśli wybierzesz odpowiedni alfabet. I nie potrzebujesz bitów do reprezentowania wykresu -vertex: macierz przylegania ma dokładnie bity.

5 c

$5c$

c n^{2} \log n

$cn^2\log n$

n

$n$

n^{2}

$n^2$

— David Richerby,

Być może kiedy użyć N lub N log L może zależeć od kosztu działania algorytmu na każdym elemencie wejściowym. Wydaje mi się, że jeśli założymy, że algorytm używa stałego czasu do wykonywania pracy na każdym elemencie wejściowym niezależnie od jego wielkości w bitach (i nie jest to nadużywane), to N jest prawdopodobnie właściwym, co powoduje O (N) . Z drugiej strony, jeśli rozmiar elementu wejściowego w bitach zwiększa koszt operacji, wówczas N log L wydaje się dokładniejszy, ponieważ powinniśmy wyrazić w górnej granicy, jakie właściwości z wkładu są zaangażowane we wzrost

— Jesus Salas

@DavidRicherby tak, jeśli wybierzesz alfabet, potrzeba symboli, ale to właśnie tam , jeśli z innych powodów mamy inny alfabet, powiedzmy binarny, ponieważ jest o wiele bardziej użyteczne móc powiedzieć potrafi zakodować wszystko w formacie binarnym bez utraty ogólności, a następnie , ale łatwo i ciekawie jest zauważyć, że stosunkowo łatwo jest to zrobić z dowolnym nieoczywistym alfabetem przy stałym współczynniku . Co prawda, możesz nie potrzebować bitów , ale jest to dość solidna górna granica, która może poradzić sobie zarówno z normalnym kodowaniem.

5

$5$

c = 1

$c=1$

c = \log_{2} 5

$c = \log_{2}5$

5

$5$

O (n^{2} \log n)

$O(n^{2}\log n)$

— Luke Mathieson,

Zależy to od twojego modelu obliczeniowego, a także niestety czasami od samego algorytmu.

Jeśli twoim modelem obliczeniowym jest maszyna Turinga , to rozmiar danych wejściowych to liczba komórek zajmowanych przez dane wejściowe. Więc jeśli twoje wejście jest wtedy wejście ma długość 6. $ababcd$
Jeśli twoim modelem jest pamięć RAM, to rozmiar danych wejściowych to liczba rejestrów / komórek pamięci, w których dane wejściowe początkowo pozostają. Może to być niewłaściwie wykorzystane, ponieważ technicznie można zapisać cały wpis w jednym rejestrze. Jednak wtedy obliczenia są bardziej kosztowne, jeśli użyjesz modelu kosztów logarytmicznych.
Jeśli twoim modelem obliczeniowym jest słowo-RAM , to również zliczasz komórki pamięci, ale mogą one przechowywać tylko liczby całkowite bit, ponieważ jest parametrem twojego modelu. $w$ $w$

Jednak wiele algorytmów nie jest mierzonych w odniesieniu do „rzeczywistego” rozmiaru wejściowego. Następnie musisz dokładnie sprawdzić, do czego odnosi się stwierdzenie analizy.

Często masz domniemane założenie dotyczące problemu. Mówiąc, że sortowanie elementów zajmuje , zakładasz, że dwa elementy można porównać w czasie . Oczywiście, jeśli posortujesz, powiedzmy bardzo długie łańcuchy, może to nie być prawda. $O(n\log n)$ $n$ $O(1)$ $n$
Z konwencjonalnych powodów czasami mierzysz w odniesieniu do innego parametru wejściowego. Na przykład mnożenie macierzy jest zazwyczaj analizowane pod kątem mnożenia dwóch macierzy . $n\times n$

Pewna zasada: używaj, co chcesz, ale wyraź to jasno w zestawieniu wyniku. Więc po prostu powiedzieć co dokładnie to, czy istnieje szansa na nieporozumieniu. $n$

— A.Schulz
źródło

Powiedz, czym jest niezależnie od tego, czy istnieje szansa na nieporozumienie! „Algorytm działa w czasie ” nie ma znaczenia, jeśli nie zostało zdefiniowane, nawet jeśli „ jest długością wejścia” jest jedynym rozsądnym domysłem.

n

$n$

O (n^{3})

$O(n^3)$

n

$n$

n

$n$

— David Richerby,