Co to jest czas pseudo wielomianowy ? Czym różni się od czasu wielomianowego? Niektóre algorytmy działające w czasie pseudo wielomianowym mają czasy wykonania, takie jak O (nW) (dla problemu plecakowego 0/1 ) lub O (√n) (dla podziału próbnego ); dlaczego to nie liczy się jako czas wielomianowy?
Odpowiedzi:
Aby zrozumieć różnicę między czasem wielomianowym a czasem pseudo wielomianowym, musimy zacząć od sformalizowania, co oznacza „czas wielomianowy”.
Powszechną intuicją dotyczącą czasu wielomianowego jest „czas O (n k ) dla jakiegoś k”. Na przykład sortowanie przez wybór przebiega w czasie O (n 2 ), który jest czasem wielomianowym, podczas gdy rozwiązanie TSP przy użyciu brutalnej siły wymaga czasu O (n · n!), Który nie jest czasem wielomianowym.
Wszystkie te środowiska wykonawcze odwołują się do zmiennej n, która śledzi rozmiar danych wejściowych. Na przykład w sortowaniu przez wybór n oznacza liczbę elementów w tablicy, podczas gdy w TSP n oznacza liczbę węzłów na grafie. W celu ujednolicenia definicji tego, co faktycznie oznacza „n” w tym kontekście, formalna definicja złożoności czasowej definiuje „rozmiar” problemu w następujący sposób:
Rozmiar wejścia do problemu to liczba bitów wymaganych do zapisania tego wejścia.
Na przykład, jeśli dane wejściowe do algorytmu sortowania są tablicą 32-bitowych liczb całkowitych, wówczas rozmiar danych wejściowych będzie wynosił 32n, gdzie n to liczba wpisów w tablicy. Na grafie z n węzłami i m krawędziami dane wejściowe mogą być określone jako lista wszystkich węzłów, po której następuje lista wszystkich krawędzi, co wymagałoby Ω (n + m) bitów.
Biorąc pod uwagę tę definicję, formalna definicja czasu wielomianowego jest następująca:
Algorytm działa w czasie wielomianowym, jeśli jego czas wykonania wynosi O (x k ) dla pewnej stałej k, gdzie x oznacza liczbę bitów danych wejściowych przekazanych do algorytmu.
Podczas pracy z algorytmami przetwarzającymi wykresy, listy, drzewa itp. Ta definicja jest mniej więcej zgodna z konwencjonalną definicją. Na przykład załóżmy, że masz algorytm sortowania, który sortuje tablice 32-bitowych liczb całkowitych. Jeśli użyjesz czegoś takiego jak sortowanie przez wybór, środowisko wykonawcze, jako funkcja liczby elementów wejściowych w tablicy, będzie wynosić O (n 2 ). Ale jak n, liczba elementów w tablicy wejściowej, odpowiada liczbie bitów danych wejściowych? Jak wspomniano wcześniej, liczba bitów danych wejściowych będzie wynosić x = 32n. Dlatego, jeśli wyrazimy czas wykonania algorytmu w postaci x zamiast n, otrzymamy, że czas wykonania wynosi O (x 2 ), a więc algorytm działa w czasie wielomianowym.
Podobnie, przypuśćmy, że na wykresie wykonujesz przeszukiwanie najpierw w głąb , co zajmuje czas O (m + n), gdzie m to liczba krawędzi na grafie, a n to liczba węzłów. Jak to się ma do liczby podanych bitów danych wejściowych? Cóż, jeśli założymy, że wejście jest określone jako lista przylegania (lista wszystkich węzłów i krawędzi), to jak wspomniano wcześniej, liczba bitów wejściowych będzie wynosić x = Ω (m + n). Dlatego środowisko wykonawcze będzie równe O (x), więc algorytm działa w czasie wielomianowym.
Sytuacja się jednak psuje, gdy zaczynamy mówić o algorytmach operujących na liczbach. Rozważmy problem sprawdzenia, czy liczba jest liczbą pierwszą, czy nie. Biorąc pod uwagę liczbę n, możesz sprawdzić, czy n jest liczbą pierwszą, używając następującego algorytmu:
function isPrime(n):
for i from 2 to n - 1:
if (n mod i) = 0, return false
return true
Jaka jest więc złożoność czasowa tego kodu? Cóż, ta wewnętrzna pętla działa O (n) razy i za każdym razem wykonuje pewną ilość pracy, aby obliczyć n mod i (jako naprawdę konserwatywna górna granica, z pewnością można to zrobić w czasie O (n 3 )). Dlatego ten ogólny algorytm działa w czasie O (n 4 ) i prawdopodobnie znacznie szybciej.
W 2004 roku trzech informatyków opublikowało artykuł zatytułowany PRIMES jest w P, podając algorytm czasu wielomianowego do sprawdzania, czy liczba jest liczbą pierwszą. Uznano to za przełomowy wynik. Więc o co chodzi? Czy nie mamy już do tego algorytmu czasu wielomianowego, mianowicie powyższego?
Niestety nie. Pamiętaj, formalna definicja złożoności czasowej mówi o złożoności algorytmu jako funkcji liczby bitów danych wejściowych. Nasz algorytm działa w czasie O (n 4 ), ale co to jest w funkcji liczby bitów wejściowych? Cóż, wypisanie liczby n wymaga O (log n) bitów. Dlatego jeśli przyjmiemy, że x będzie liczbą bitów wymaganych do wypisania wejścia n, czas działania tego algorytmu wynosi w rzeczywistości O (2 4x ), co nie jest wielomianem w x.
To jest sedno rozróżnienia między czasem wielomianowym a czasem pseudo-wielomianowym. Z jednej strony naszym algorytmem jest O (n 4 ), które wygląda jak wielomian, ale z drugiej strony, zgodnie z formalną definicją czasu wielomianu, nie jest to czas wielomianowy.
Aby zorientować się, dlaczego algorytm nie jest algorytmem wielomianowym, pomyśl o następujących kwestiach. Załóżmy, że chcę, aby algorytm musiał wykonać dużo pracy. Jeśli napiszę takie dane wejściowe:
10001010101011
to zajmie trochę czasu, powiedzmy T, w najgorszym przypadku . Jeśli teraz dodam jeden bit na końcu numeru, w ten sposób:
100010101010111
Czas działania będzie teraz (w najgorszym przypadku) wynosić 2T. Mogę podwoić ilość pracy wykonywanej przez algorytm, dodając jeszcze jeden bit!
Algorytm działa w czasie pseudo wielomianu, jeśli czas wykonania jest jakimś wielomianem w wartości liczbowej wejścia , a nie w liczbie bitów wymaganych do jego przedstawienia. Nasz główny algorytm testujący jest algorytmem pseudopolimianu czasu, ponieważ działa w czasie O (n 4 ), ale nie jest algorytmem wielomianu, ponieważ w zależności od liczby bitów x wymaganych do wypisania danych wejściowych, czas wykonania wynosi O (2 4x ). Powodem, dla którego artykuł „PRIMES is in P” był tak znaczący, było to, że jego czas działania wynosił (w przybliżeniu) O (log 12 n), co w funkcji liczby bitów wynosi O (x 12 ).
Więc dlaczego to ma znaczenie? Cóż, mamy wiele algorytmów czasu pseudopolynomianu do faktoryzacji liczb całkowitych. Jednak te algorytmy są, mówiąc technicznie, algorytmami czasu wykładniczego. Jest to bardzo przydatne w kryptografii: jeśli chcesz używać szyfrowania RSA, musisz mieć zaufanie, że nie możemy łatwo uwzględniać liczb. Zwiększając liczbę bitów w liczbach do ogromnej wartości (powiedzmy 1024 bity), można sprawić, że ilość czasu, jaką musi zająć algorytm faktorowania pseudopolimianu, stanie się tak duża, że byłoby całkowicie i całkowicie niewykonalne uwzględnienie liczby. Jeśli, z drugiej strony, możemy znaleźć algorytm faktoryzacji wielomianu w czasie , niekoniecznie tak jest. Dodanie większej liczby bitów może spowodować znaczny wzrost pracy, ale wzrost będzie tylko wzrostem wielomianowym, a nie wykładniczym.
To powiedziawszy, w wielu przypadkach algorytmy czasu pseudo wielomianowego są całkowicie dobre, ponieważ rozmiar liczb nie będzie zbyt duży. Na przykład sortowanie zliczające ma czas wykonania O (n + U), gdzie U jest największą liczbą w tablicy. Jest to czas pseudowielomianu (ponieważ wartość liczbowa U wymaga O (log U) bitów do wypisania, więc czas wykonywania jest wykładniczy pod względem wielkości wejściowej). Jeśli sztucznie ograniczymy U, aby U nie było zbyt duże (powiedzmy, jeśli pozwolimy U wynosić 2), to czas wykonania wynosi O (n), co w rzeczywistości jest czasem wielomianowym. Oto, jak działa sortowanie radix : przetwarzając liczby po jednym bicie, czas wykonania każdej rundy wynosi O (n), więc całkowity czas wykonania wynosi O (n log U). To faktycznie jest czas wielomianowy, ponieważ wypisanie n liczb do sortowania wykorzystuje Ω (n) bitów, a wartość log U jest wprost proporcjonalna do liczby bitów wymaganych do wypisania maksymalnej wartości w tablicy.
Mam nadzieję że to pomoże!
isPrimezłożoność jest szacowana jako O (n ^ 4), a nie po prostu O (n)? Nie rozumiem. Chyba że złożoność n mod iwynosi O (n ^ 3) .... co z pewnością nie jest.
n mod ijest zbyt konserwatywne. Czas modjest funkcją liczby bitów n, a nie nsamego siebie, więc powinien wynosić O ((log n) ^ 3).
Pseudo-wielomianowa złożoność czasowa oznacza wielomian wartości / wielkości danych wejściowych, ale wykładniczy pod względem wielkości danych wejściowych.
Przez rozmiar rozumiemy liczbę bitów wymaganych do zapisania danych wejściowych.
Z pseudo-kodu plecaka możemy znaleźć złożoność czasową O (nW).
// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n) //
Knapsack capacity (W)
for w from 0 to W
do m[0, w] := 0
end for
for i from 1 to n do
for j from 0 to W do
if j >= w[i] then
m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
else
m[i, j] := m[i-1, j]
end if
end for
end for
Tutaj jednak W nie jest wielomianem długości wejścia, co czyni go pseudo-wielomianem.
Niech będzie liczbą bitów potrzebnych do reprezentacji W.
i.e. size of input= s =log(W) (log= log base 2)
-> 2^(s)=2^(log(W))
-> 2^(s)=W (because 2^(log(x)) = x)
Teraz running time of knapsack= O (nW) = O (n * 2 ^ s), co nie jest wielomianem.