11190 Str013 (2)

i* t, Kilka nfidnleil ctemfntamej teorii licrh

ośmiok rolne zwiększenie wari ości /. Relacja/(n) = Oflag* n) (gdzie piszemy log^-n dla oznaczenia (iogn)'*) oznacza, że funkcja / rośnie w przybliżeniu tak szybko jak d ta potęga liczby cyfr dwójkowych zmiennej n. Jest tak dlatego, że z dokładnością do stałej multyplikatywncj liczba cyfr dwójkowych jest w przybliżeniu równa Iogn (mianowicie różni się o mniej niż 1 od logn/log2»

== 1,4427Iogn). Zatem, na przykład, jeśli/(«) = 0(log³n), to podwojenie liczby bitów liczby n (co jest oczywiście znacznie bardziej drastycznym zwiększeniem wielkości liczby n niż po prostu podwojenie samej tej liczby) zwiększy wartość/mniej więcej ośmiokrotnie.

Zauważmy, że zapis /(n)=0( 1) oznacza, iż funkcja/jest ograniczona przez pewną stałą.

Uwaga. Widzieliśmy, że jeśli chcemy pomnożyć dwie liczby mniej więcej tej samej wielkości, to możemy skorzystać z oszacowania

Czas (liczba k-bitowa • liczba k-bitowa) = 0(k²).

Warto zauważyć tu, że wiele pracy poświęcono problemowi zwiększenia szybkości mnożenia liczb k-cyfrowych dla dużych k. Bardzo wyrafinowane techniki mnożenia, znacznie wykraczające poza metody szkolne, których tu używaliśmy, umożliwiły matematykom znalezienie takiej procedury wykonującej mnożenie liczb k-cyfrowych, która wymaga jedynie O(klogfcloglogk) operacji na bitach. Jest to lepiej niż 0(k²), a nawet lepiej niż 0(k^1+e) dla dowolnie małej liczby e > 0. Jednakże w dalszym ciągu zadowolimy się znacznie mniej dokładnym, poprzednim oszacowaniem czasu potrzebnego do wykonania mnożenia.

Na ogół, jeśli szacujemy liczbę operacji na bitach potrzebnych do wykonania jakiegoś zadania, to pierwszy krok polega na wybraniu i zapisaniu zarysu szczegółowej procedury, za pomocą której wykonamy to zadanie. Dokładny opis, krok po kroku, procedury wykonującej obliczenia nazywamy algorytmem. Oczywiście może istnieć wiele algorytmów wykonujących to samo zadanie. Możemy wybrać ten algorytm, który najłatwiej zapisać, lub możemy wybrać algorytm działający najszybciej ze wszystkich znanych algorytmów albo możemy wybrać rozwiązanie kompromisowe, polegające na znalezieniu pewnej równowagi między szybkością i prostotą. Użyty wyżej algorytm do mnożenia n przez m jest dużo wolniejszy od najszybszych znanych algorytmów. Ale z pewnością jest znacznie szybszy niż algorytm polegający na wielokrotnym dodawaniu (dodawaniu liczby n do siebie m razy).

Przykład 10. Oszacujmy czas potrzebny do zamiany podstawy liczby fc-cyf-rowej z systemu dwójkowego na system dziesiętny.

Rozwiązanie. Niech n będzie liczbą k-cyfrową zapisaną w systemie dwójkowym. Algorytm zamiany podstawy działa w następujący sposób. Dzielimy

n przez 10 = (1010)₂. Reszta, która będzie jedna z liczb: 0,1, 10, 11, 100,101, 110,111,1000 lub 1001, będzie cyfrą jedności d^. Następnie zastępujemy liczbę n otrzymanym ilorazem i powtarzamy cały proces: dzielimy iloraz przez (1010)₂, bierzemy resztę jako d_} i iloraz jako następną liczbę, którą będziemy dzielić przez (1010)₂. To postępowanie musi być powtórzone tyle razy, ile cyfr

dziesiętnych ma liczba n, tzn.

+ 1 = O(k). Wtedy kończymy wyko

Iogn

loglO

nanie algorytmu. (Możemy oczywiście otrzymane cyfry dziesiętne, tzn. kolejne reszty z dzielenia, zapisać w zwyczajny sposób, zastępując 0, 1, 10, 11, 100, 101, 110, 111, 1000 i 1001 odpowiednio cyframi 0,1,2,3,4, 5, 6, 7, 8 i 9). Ile operacji na bitach wykonamy w ten sposób? Mamy O(k) dzieleń, każde wymagające 0(4k) operacji na bitach (dzielimy liczbę mającą co najwyżej k cyfr binarnych przez liczbę czterocyfrową (1010)₂). Ale 0(4k) jest tym samym co 0(k) (czynniki stale nie mają wpływu na O), zatem ostatecznie stwierdzamy, że liczba operacji wynosi 0(k) • 0(k) - 0(k²). Jeśli chcemy wyrazić tę równość za pomocą samej liczby n, a nie za pomocą k, to uwzględniając równość k = O (Iogn), otrzymamy

Czas (zamiana podstawy liczby n na dziesiętną) — 0(log²/z).

Przykład 11. Oszacujmy czas potrzebny do zamiany podstawy liczby k-cyfrowej z systemu dwójkowego na system pozycyjny o podstawie b, gdzie b może być bardzo dużą liczbą.

Rozwiązanie. Użyjemy tego samego algorytmu co w przykładzie 10, z tą tylko różnicą, że będziemy dzielić przez liczbę /-cyfrową b. Stwierdzimy, że dzielenie trwa dłużej (jeśli liczba / jest duża), wymaga mianowicie O (ki) operacji na bitach. Ale ile razy będziemy dzielić? Zauważmy, że liczba cyfr liczby n zapisanej w systemie o podstawie b wynosi Oikfl) (por. przykład 9(c)). Zatem łączna liczba operacji na bitach, koniecznych do wykonania wszystkich potrzebnych dzieleń, wyniesie 0(k/l) • O (ki) = 0(k^z). Okazuje się, że jest to ta sama odpowiedź co w przykładzie 10. A więc nasze oszacowanie czasu zamiany podstawy nie zależy od wyboru podstawy, na którą zamieniamy liczbę (nie ma przy tym znaczenia, jak duża jest ta podstawa). Jest tak dlatego, że większy czas potrzebny do znalezienia każdej cyfry jest równoważony tym, że musimy znaleźć mniej cyfr.

Przykład 12. Wyraźmy za pomocą notacji O czas potrzebny do obliczenia (a) ni, (b) (por. przykłady 6 i 8).

Rozwiązanie, (a) 0(n² log²n), (b) 0(m²\og²n).

Na zakończenie tego podrozdziału podamy definicję o podstawowym znaczeniu w informatyce i w teorii algorytmów.