Złożoność algorytmu dla danych wejściowych n-cyfrowych

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?

http://en.wikipedia.org/wiki/Trial_division#Speed

Dzięki za link, wciąż jednak to nie wyjaśnia, jak możemy badać złożoność innych algorytmów, niekoniecznie dotyczących faktoryzacji. Byłoby dobrze, gdyby ktoś pokazał to na prostym przykładzie.

Oszacowanie złożoności asymptotycznej
Złożoność czasowa
http://4programmers.net/Forum/Algorytmy/152048-problemy_z_obliczaniem_zlozonosci
Złożoność obliczeniowa algorytmów.
http://4programmers.net/Forum/Algorytmy/222128-liczba_automorficzna_-_poprawnosc_i_zlozonosc
i tysiąc innych ...

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(n^k) 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ć ;)

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=2^k czyli jest liczbą binarną reprezentowaną na k bitach. Wtedy złożoność naiwnego algorytmu to O(sqrt(n)) = O(sqrt(2^k)) = O(2^k/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 2ⁱ 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ę?

Rozumiem, że dla n=2^k otrzymamy: O(log₂(n)^m) = O(log₂(2^k)^m) = O(k^m), 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 = 2^k i przeliczyć?
Zostaje jedno pytanie, czy O(a^k*n) = O(aⁿ) dla pewnych stałych a, k?

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 :)
2. Nie, a przynajmniej nie do końca. O(a^k*n) dla ustalonych a oraz k jest równoważne O(bⁿ) gdzie b=a^k
   Oczywiście nasze b jest tu stałą, ale nie jest to stała równa a ;)