ου γαρ εστιν κρυπτον ο ου φανερον γενησεται ουδε αποκρυφον ο ου γνωσθησεται και εις φανερον ελθη
Wersja PL ENG Version

Szacowanie czasu działań matematycznych

Określenie czasu potrzebnego na wykonanie przez komputer dowolnego zadania, można przeprowadzić szacując liczbę wymaganych operacji na bitach. Analizuje się wtedy, ile zmian bitów jest potrzebnych do wykonania danego działania na liczbie, która jest przechowywana w komputerze w zapisie dwójkowym.

Dodawanie liczb binarnych

Dodawanie dwóch liczb w naturalnym systemie dwójkowym (ang. NBS - Natural Binary System) można przedstawić za pomocą prostego dodawania pisemnego:

 111   
  11100
+ 01110
 101010

Krótszą liczbę uzupełnia się zerami, tak aby obie liczby miały taką samą długość k bitów. Następnie dla każdej pary cyfr przeprowadza się proste pisemne sumowanie, przenosząc 1 do kolejnej kolumny, jeśli wynik dodawania jest większy niż 1.

Wynik sumowania dwóch k-cyfrowych liczb ma długość k lub k+1, a cała operacja dodawania wymaga k operacji na bitach.

Mnożenie liczb binarnych

Analogicznie do dodawania, można mnożyć pisemnie dwie liczby binarne:

    11101
  x 01111
    11101
  111010 
+11101   
101111001

Przy mnożeniu dwóch liczb binarnych nm o długościach odpowiednio kj bitów otrzymuje się co najwyżej j wierszy (ilość wierszy jest równa ilości jedynek w liczbie m) zawierających kopie liczby n przesuniętą w lewo o odpowiednią liczbę cyfr. Całe mnożenie polega więc na wykonaniu maksymalnie j-1 dodawań, z których każda wymaga przeprowadzenia k operacji na bitach.

Całkowieta ilość operacji na bitach przy mnożeniu dwóch liczb binarnych jest mniejsza niż iloczyn ich długości. Wynik działania ma długość równą sumie długości dwóch liczb lub mniejszą o 1 od tej sumy.

W tym miejscu należy stwierdzić, że istnieją bardziej wydajne techniki mnożenia dużych liczb, które pozwalają wykonywać te operacje o wiele szybciej. Znane są algorytmy mnożące dwie liczby k-cyfrowe, które wymagają jedynie wykonania k(ln k)(ln (ln k)) operacji na bitach.

Silnia

Silnia liczby naturalnej n (n!) to iloczyn wszystkich liczb naturalnych nie większych niż n.

Iloczyn n liczb o długości k ma co najwyżej nk bitów. Liczba n! ma wobec tego również co najwyżej nk bitów. W celu obliczenia n! należy wykonać n-2 mnożeń liczb o długości maksymalnie k bitów przez liczbę o długości maksymalnie nk bitów.

Łączna ilość operacji na bitach wynosi wobec tego:
    (n-2)nk2

Liczbę tę można przedstawić za pomocą zależności wyłącznie od n:
    (n-2)n([log2n]+1)2

W przybliżeniu:
    n2(log2n)2

Czas wielomianowy

Według twierdzenia Cobham'a (ang. Cobham's thesis), algorytmy uznawane są za szybkie i efektywne, jeśli działają w czasie wielomianowym.

Definicja Algorytm wykonujący obliczenia na liczbach n1, n2, ..., nr, mających odpowiednio k1, k2, ..., kr cyfr, działa w czasie wielomianowym, jeśli istnieją liczby całkowite d1, d2, ..., dr takie, że liczba operacji na bitach potrzebnych do wykonania tego algorytmu wynosi O(k1d1  k2d2  ...  krdr).
  • Działania dodawania, odejmowania, mnożenia i dzielenia są algorytmami działającymi w czasie wielomianowym
  • Zmiana podstawy jest algorytmem działającym w czasie wielomianowym
  • Algorytm obliczający n! nie działa w czasie wielomianowym