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:
| 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 0 | 0 | ||
| + | 0 | 1 | 1 | 1 | 0 | |
| 1 | 0 | 1 | 0 | 1 | 0 |
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:
| 1 | 1 | 1 | 0 | 1 | ||||
| x | 0 | 1 | 1 | 1 | 1 | |||
| 1 | 1 | 1 | 0 | 1 | ||||
| 1 | 1 | 1 | 0 | 1 | 0 | |||
| + | 1 | 1 | 1 | 0 | 1 | |||
| 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
Przy mnożeniu dwóch liczb binarnych n i m o długościach odpowiednio k i j 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.
- 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
