Cześć, jak sprawdzić czy dany algorytm, przyjmujący na wejściu jedną liczbę, działa w czasie wielomianowym względem ilości cyfr tej liczby?
W szczególności - jak sprawdzono, że najprostszy algorytm faktoryzacji, sprawdzający podzielność liczby n przez 1, 2, ..., sqrt(n), działa w czasie wykładniczym wobec długości liczby n?
- Rejestracja:ponad 12 lat
- Ostatnio:ponad rok
- Postów:18
0
- Rejestracja:około 21 lat
- Ostatnio:prawie 3 lata
- Lokalizacja:Space: the final frontier
- Postów:26433
- Rejestracja:około 21 lat
- Ostatnio:prawie 3 lata
- Lokalizacja:Space: the final frontier
- Postów:26433
- Rejestracja:ponad 12 lat
- Ostatnio:ponad rok
- Postów:18
0
Zadam trochę inne pytanie. Ogólnie rzecz biorąc chodzi mi o problemy NP. Na wiki możemy poczytać o takim problemie:
Czy jakikolwiek podzbiór zadanego zbioru (np. {-2,6,-3,72,10,-11}) sumuje się do zera?
Jeżeli dla n dowolnych liczb na wejściu znajdziemy algorytm o złożoności O(nk) dla pewnego, ustalonego k to będzie to rozwiązanie problemu NP.
Czy w przypadku algorytmu faktoryzacji, będzie on rozwiązaniem problemu NP, wtedy gdy będzie miał złożoność postaci O(log(n)k) dla pewnego k?
Jeśli tak, to dlaczego podany algorytm o złożoności O(sqrt(n)) = O(n(1/2)) nie jest rozwiązaniem, pomimo tego, że jest to postać wielomianowa?
Podobnym zadaniem jest sprawdzenie czy dana liczba jest pierwsza. Teoretycznie, w przypadku tego samego algorytmu złożoność wynosi O(n(1/2)). Jednak dopiero w 2002 roku przyznano nagrodę za rozwiązanie problemu "wielomianowego testu pierwszości". Pokazano wówczas, że można to zrobić w czasie O(log(n)(21/2)).
Artykuł o tym algorytmie: http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf
WIKI: http://en.wikipedia.org/wiki/AKS_primality_test
Na wiki jest napisane:
"AKS is the first primality-proving algorithm to be simultaneously general, polynomial, deterministic, and unconditional. Previous algorithms had been developed for centuries and achieved three of these properties at most, but not all four."
Ten zwykły algorytm też spełnia te warunki.
Nie do końca chyba rozumiem przesłany przez Ciebie artykuł, kwestię problemów NP albo sam nie wiem o co chcę spytać ;)
edytowany 2x, ostatnio: AKZ
- Rejestracja:około 21 lat
- Ostatnio:prawie 3 lata
- Lokalizacja:Space: the final frontier
- Postów:26433
1
Twój błąd polega na tym ze patrzysz na złożoność względem liczby n a nie względem rozmiaru reprezentacji binarnej liczby n. Niech n=2k czyli jest liczbą binarną reprezentowaną na k bitach. Wtedy złożoność naiwnego algorytmu to O(sqrt(n)) = O(sqrt(2k)) = O(2k/2) czyli jak widać jest wykładnicza względem liczby bitów w reprezentacji danej liczby.
Bardziej intuicyjnie: zauważ ze dodanie kolejnej cyfry/kolejnego bitu do danej liczby to jest pomnożenie jej przez 2, czyli dodanie każdych i bitów powoduje 2i wzrost analizowanej liczby, czyli liczba rośnie nam wykładniczo, wiec i czas szukania algorytmem naiwnym (który jest trochę szybszy niż liniowy) rośnie nam wykładniczo.
Podany przez ciebie algorytm AKS działa w czasie wielomianowym względem liczby bitów reprezentacji danej liczby a nie względem liczby. Widzisz różnicę?
edytowany 1x, ostatnio: Shalom
- Rejestracja:ponad 12 lat
- Ostatnio:ponad rok
- Postów:18
0
Rozumiem, że dla n=2k otrzymamy: O(log2(n)m) = O(log2(2k)m) = O(km), stąd jest to algorytm wielomianowy? Więc jeśli chcę zbadać złożoność algorytmu względem liczby bitów reprezentacji liczby n, muszę wstawić do funkcji n = 2k i przeliczyć?
Zostaje jedno pytanie, czy O(ak*n) = O(an) dla pewnych stałych a, k?
edytowany 1x, ostatnio: AKZ
- Rejestracja:około 21 lat
- Ostatnio:prawie 3 lata
- Lokalizacja:Space: the final frontier
- Postów:26433
1
- Tak, jeśli chcesz bawić się w analizę względem długości reprezentacji to musisz jako zmiennej używać właśnie takiego wykładniczego zapisu :)
- Nie, a przynajmniej nie do końca. O(ak*n) dla ustalonych
aorazkjest równoważne O(bn) gdzie b=ak
Oczywiście naszebjest tu stałą, ale nie jest to stała równaa;)