Matematyka.pl

Chciałbym zrozumieć jak się liczy złożoność algorytmów, zwłaszcza algorytmów faktoryzacji liczb złożonych. Co to znaczy, że algorytm działa w czasie \(\displaystyle{ O(n^2)}\) na przykład? Nie wiem co oznacza to \(\displaystyle{ n}\). Czy to jest wielkość liczby, czy liczba cyfr? I podobno to też jakoś w systemie binarnym się przedstawia. Weźmy na przykład taki najprostszy algorytm faktoryzacji kolejnych dzieleń. Czy on działa w czasie \(\displaystyle{ O( \sqrt{n}) }\)? Czyli jak wezmę jakąś liczbę \(\displaystyle{ n}\) to po jakim czasie dostanę odpowiedź? Jeśli ktoś mógłby mi trochę przybliżyć temat będę wdzięczny.

Dodano po 1 dniu 14 godzinach 45 minutach 32 sekundach:
Czy może się ktoś wypowiedzieć?

Trzeba było na wykładzie uważać. Albo do książki zajrzeć. Sorry, max, ale coś musisz sam zrobić...

Ale mógłbyś wnieść jakiś merytoryczny komentarz do sprawy, który coś wnosi, a nie tak spamujesz. Mam prawo czegoś nie wiedzieć, matematyka to bardzo szeroka nauka. Zwróciłem się z prośbą o pomoc w tym temacie, to chyba nic złego.

Z przyczyn praktycznych i teoretycznych interesuje nas ile działań arytmetycznych (dodawań, mnożeń,...) ogólnie operacji standardowych (ops) wystarczy do rozwiązania danego zadania numerycznego określonej klasy oraz czy istnieje algorytm optymalny, który rozwiązuje zadanie tej klasy minimalnym kosztem?

Problemem tym zajmuje się teoria złożoności obliczeniowej.

Złożoność obliczeniowa algorytmu numerycznego zależy zwykle od rozmiaru rozwiązywanego zadania numerycznego na przykład od stopnia wielomianu w przypadku wyznaczania zer wielomianu, czy od liczby równań w przypadku zadania rozwiązywania układu liniowych równań algebraicznych.

Charakterystyki złożoności są więc funkcjami rzeczywistymi zmiennej rzeczywistej typu: \(\displaystyle{ f : \NN \rightarrow \RR. }\)

Do ich klasyfikacji służy pojęcie rzędu funkcji.

Funkcja \(\displaystyle{ f:\NN \rightarrow \RR }\) jest rzędu \(\displaystyle{ g: \NN \rightarrow \RR }\) co zapisujemy \(\displaystyle{ f\in O(g(x) }\), jeżeli

\(\displaystyle{ \exists \ \ C\in \RR_{+} \ \ \exists \ \ N\in \NN \ \ \forall n> N :|f(n)|\leq C|g(n)|}\) albo \(\displaystyle{ \lim_{n\to \infty} \left|\frac{f(n)}{g(n)} \right| < \infty }\)

Na przykład funkcja \(\displaystyle{ f(n) = n\cdot \ln(n) }\) jest rzędu \(\displaystyle{ O(n^2), }\) co zapisujemy \(\displaystyle{ n\cdot \ln(n) \in O(n^2). }\)

Funkcją złożoności obliczeniowej algorytmu \(\displaystyle{ \mathcal{A} }\) rozwiązywania klasy zadań numerycznych nazywamy następującą funkcję wymiaru zadania \(\displaystyle{ n }\)

\(\displaystyle{ f_{\mathcal{A}} (n) = \sup (OPS(x): \vec{x} \in D_{n}) }\)

gdzie \(\displaystyle{ OPS(x) }\) jest liczbą operacji standardowych (elementarnych) niezbędnych do rozwiązania zadania za pomocą algorytmu \(\displaystyle{
\mathcal{A} }\) dla danych \(\displaystyle{ \vec{x} }\) należących do zbioru danych \(\displaystyle{ D_{n}.}\)

Ze względu na złożoność obliczeniową algorytmy numeryczne dzielimy na:

-algorytmy wielomianowe (efektywne) dla których:

\(\displaystyle{ f_{\mathcal{A}} \in O \left (\sum_{k=0}^{K}\alpha_{k}n^{k}\right) }\)

algorytmy wykładnicze (nieefektywne) dla których:

\(\displaystyle{ f_{\mathcal{A}} \notin O \left (\sum_{k=0}^{K}\alpha_{k}n^{k}\right) }\)

Porównanie złożoności obliczeniowej algorytmów wielomianowych i wykładniczych (czasy wykonania algorytmu) ilustruje tabela:

\(\displaystyle{ \begin{tabular}{|c|c|c|} \hline
f_{\mathcal{A})}(n) & n=10 & n=60 \\ \hline
O(n) & 0,0001s & 0,00006 s \\ \hline
O(n^3) & 0,001s & 0,216 s \\ \hline
O(n^5) & 0,1 s & 13min \\ \hline
O(2^{n}) & 0,001 s & 3366 stuleci \\ \hline
O(3^{n}) & 0,059s & 1,3\cdot 10^{13} stuleci \\ \hline
\end{tabular} }\)

Dla zainteresowanych pełniejszym zapoznaniem się z tą problematyką proponuję:

J. Błażewicz, Złożoność obliczeniowa problemów kombinatorycznych . WNT. Warszawa 1988.

J.F. Traub, H. Wożniakowski , Information Uncertainly, Complexity. Addison -Wesley 1983.

Herbert S. Wilf, ALGORITHMS AND COMPLEXITY. University of Pennsylvania. Philadelphia 1994.